Cod sursa(job #2051465)

Utilizator Liviu_Ionut_MoantaMoanta Ionut Liviu Liviu_Ionut_Moanta Data 29 octombrie 2017 00:05:18
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int n,i,st,dr,mid;
int v[30005],poz[30005],aib[30005];
void update(int p,int val){
    for(;p<=n;p+=(p&-p)){
        aib[p]+=val;
    }
}
int query(int p){
    int r=0;
    for(;p;p-=(p&-p)){
        r+=aib[p];
    }
    return r;
}
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
        update(i,1);
    }
    for(i=n;i>=1;i--){
        st=1;
        dr=n;
        while(st<=dr){
            mid=(st+dr)/2;
            if(query(mid)<v[i]){
                st=mid+1;
            }
            else{
                dr=mid-1;
            }
        }
        poz[st]=i;
        update(st,-1);
    }
    for(i=1;i<=n;i++){
        fout<<poz[i]<<"\n";
    }
    return 0;
}