Cod sursa(job #858355)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 18 ianuarie 2013 20:41:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#define Nmax (1<<15)
#define lsb(x) (x&-x)
using namespace std;

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

void Update(int Nod,int Val) {

    for(;Nod<=N;Nod+=lsb(Nod))
        Aib[Nod]+=Val;

}
int Query(int Nod) {

    int Ans=0;

    for(;Nod;Nod-=lsb(Nod))
        Ans+=Aib[Nod];

    return Ans;

}
int BinarySearch(int Val) {

    int i,Step;

    for(i=N,Step=Nmax;Step;Step>>=1)
        if(i-Step>=1 && Query(i-Step)>=Val)
            i-=Step;

    return i;

}
void Solve() {

    int i,Ans;

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

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

}
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;

}