Cod sursa(job #858387)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 18 ianuarie 2013 20:56:40
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb

#include <fstream>
#define Nmax (1<<17)
#define lsb(x) (x&-x)
using namespace std;

int N,V[Nmax],Sol[Nmax],Arb[Nmax];

void Update(int Nod,int K,int Left,int Right,int Val) {

    if(Left==Right) {
        Arb[Nod]=Val;
        return;
        }

    int Mid=(Left+Right)>>1;

    if(K<=Mid)  Update(2*Nod,K,Left,Mid,Val);
    else        Update(2*Nod+1,K,Mid+1,Right,Val);

    Arb[Nod]=Arb[2*Nod]+Arb[2*Nod+1];

}
int Query(int Nod,int Left,int Right,int Val) {

    if(Left==Right)
        return Right;

    int Mid=(Left+Right)>>1;

    if(Val<=Arb[2*Nod]) return Query(2*Nod,Left,Mid,Val);
    else                return Query(2*Nod+1,Mid+1,Right,Val-Arb[2*Nod]);

}
void Solve() {

    int i,Ans;

    for(i=1;i<=N;i++)
        Update(1,i,1,N,1);

    for(i=N;i;i--) {
        Sol[Ans = Query(1,1,N,V[i])]=i;
        Update(1,Ans,1,N,0);
        }

}
void Read() {

    ifstream in("schi.in");

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

    in.close();

}
void Write() {

    ofstream out("schi.out");
    for(int i=1;i<=N;i++)
        out<<Sol[i]<<'\n';
    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;

}