Cod sursa(job #381191)

Utilizator vladiiIonescu Vlad vladii Data 9 ianuarie 2010 16:22:16
Problema Schi Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
using namespace std;

int poz, x, Arb[65600];

void update(int nod, int left, int right, int x){
    if (left==right) {
         Arb[nod]=x;
         return;
    }
    
    int mij=(left+right)>>1;
    if (poz<=mij) { update(2*nod, left, mij, x); }
    else { update(2*nod+1, mij+1, right, x); }
    
    Arb[nod]=Arb[2*nod]+Arb[2*nod+1];
}

void query(int nod, int left, int right, int x){
    if (left==right) {
         poz=left;
         return;
    }
    
    int mij=(left+right)>>1;
    if (Arb[nod*2]<x){
         x-=Arb[2*nod]; 
         query(2*nod+1, mij+1, right, x);
    }
    else query(2*nod, left, mij, x);
}

int main(){
    fstream f1, f2;
    int n,i,a[30005],loc[30005];
    f1.open("schi.in", ios::in);
    f1>>n;
    for(i=1; i<=n; i++) {
         f1>>a[i];
    }
    f1.close();
    for(i=1; i<=n; i++) {
         x=1; poz=i;
         update(1, 1, n, 1);
    }
    for (i=n;i>0;--i){
         query(1, 1, n, a[i]);
         loc[poz]=i;
         update(1, 1, n, 0);
    }
    f2.open("schi.out", ios::out);
    for (i=1; i<=n; i++) { f2<<loc[i]<<endl; }
    f2.close();
    return 0;
}