Cod sursa(job #1512218)

Utilizator enedumitruene dumitru enedumitru Data 27 octombrie 2015 19:51:14
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
using namespace std;
ifstream f("schi.in"); ofstream g("schi.out");
int n,AIB[30001],V[30001],sol[30001];
inline int zero(int x) {return x & (-x);}
void update(int poz, int val) {for(;poz<=n;poz+=zero(poz)) AIB[poz]+=val;}
int query(int poz)
{   int s=0;
    for(;poz;poz-=zero(poz)) s+=AIB[poz];
    return s;
}
int bs(int val)
{   int st=1,dr=n,sol=n;
    while(st<=dr)
    {   int mij=(st+dr)/2;
        if(query(mij)>=val) {sol=mij; dr=mij-1;} else st=mij+1;
    }
    return sol;
}
int main ()
{   f>>n;
    int i;
    for(i=1;i<=n;i++) {f>>V[i]; update (i,1);}
    for(i=n;i;i--) {int poz=bs(V[i]); sol[poz]=i; update(poz,-1);}
    for(i=1;i<=n;i++) g<<sol[i]<< '\n';
    g.close(); return 0;
}