Cod sursa(job #1409869)

Utilizator AndyCatrunaCatruna Andy AndyCatruna Data 30 martie 2015 19:08:50
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#define dim 30005
#define bit(x) (x&(-x))
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int n,i,j,A[dim],v[dim],s[dim],y;
void update(int val, int x){
    for(int i=x;i<=n;i+=bit(i)){
        A[i]+=val;
    }
}
int query(int x){
    int sol=0;
    for(int i=x;i>=1;i-=bit(i)){
        sol+=A[i];
    }
    return sol;
}
int cautare(int x){
    int st = 1, dr = n, sol;
    while(st<=dr){
        int mid = (st+dr)/2;
        if(query(mid)>=x){
            sol=mid;
            dr=mid-1;
        }
        else{
            st=mid+1;
        }
    }
    return sol;

}
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
        update(1,i);
    }
    for(i=n;i>=1;i--){
        y=cautare(v[i]);
        update(-1,y);
        s[y]=i;
    }
    for(i=1;i<=n;i++){
        fout<<s[i]<<" ";
    }



    return 0;
}