Cod sursa(job #1036833)

Utilizator mazaandreiAndrei Mazareanu mazaandrei Data 19 noiembrie 2013 17:35:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
using namespace std;
ifstream in("schi.in"); ofstream out("schi.out");
int sol[30001],a[30001],n,nr,poz;
int c[30001];
void update(int poz, int val){
    for(int i=poz; i<=n; i+= (i & -i)) c[i]+=val;
}
int caut(int poz){
    int i=0,step,s=0;
    for (i=0,step=1<<16;step;step>>=1)
        if((i+step<=n)&&(c[i+step]+s<poz))
            s+=c[i+step],i+=step;
    return i+1;
}
int main(){
    in>>n;
    for(int i=1;i<=n;++i) in>>a[i];
    for(int i=1;i<=n;++i) c[i]=(i & -i);
    for(int i=n;i>=1;--i){
        poz=caut(a[i]);
        sol[poz]=i;
        update(poz,-1);
    }
    for(int i=1;i<=n;++i) out<<sol[i]<<'\n';
    out.close();
    return 0;
}