Cod sursa(job #883165)

Utilizator Theorytheo .c Theory Data 19 februarie 2013 19:44:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<fstream>

#define LeftSon (Nod << 1)
#define RightSon ((Nod << 1) + 1)

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

const int Nmax = 30009;

int N; int V[Nmax]; int Pos[Nmax]; int A[Nmax << 2];


void Read(){

    fin >>N ;
    for(int i = 1; i <= N; ++i)  fin >>V[i];
}

void Init(int Nod, int st, int dr){

    if(st == dr) {A[Nod] = 1; return;}

    int m = (st + dr) >> 1;

    Init(LeftSon, st, m); Init(RightSon, m + 1, dr);
    A[Nod] = A[LeftSon] + A[RightSon];
}

int find(int Nod, int st, int dr, int Val){

    if(st == dr)
        return st;
    int m  = (st + dr) >> 1;
    if(Val <= A[LeftSon]) return find(LeftSon, st, m, Val);
    else return find(RightSon, m + 1, dr, Val - A[LeftSon]);
}

void Mark(int Nod, int st, int dr, int p){
    if(st == dr){
        A[Nod] = 0; return ;
    }
    int m = (st + dr) >> 1;
    if(p <= m)  Mark(LeftSon, st, m, p);
    else Mark(RightSon, m + 1, dr, p);

    A[Nod] = A[RightSon] + A[LeftSon];
}

void Solve(){

    Init(1, 1, N);

    for(int i = N; i ; --i){
        int X = find(1, 1, N, V[i]); Pos[X] = i; Mark(1, 1, N, X);
    }

}

void Print(){

    for(int i = 1; i <= N; ++i) fout << Pos[i] <<'\n';
}

int main(){

    Read(); Solve (); Print();
    return 0;
}