Cod sursa(job #2944185)

Utilizator Silviu_StefanStefan Silviu Silviu_Stefan Data 22 noiembrie 2022 09:56:20
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

using namespace std;
int v[30005],sol[30005];
int aib[30005];
void update(int poz,int val){
    while(poz<=30000){
        aib[poz]+=val;
        poz+=poz&-poz;
    }
}
int query(int poz){
    int cnt=0;
    while(poz>0){
        cnt+=aib[poz];
        poz-=poz&-poz;
    }
    return cnt;
}
int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    int n;fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];update(i,1);
    }
    for(int i=n;i>=1;i--){
        int st=1,dr=n,mij,val=-1;
        while(dr>=st){
            mij=(st+dr)/2;
            if(query(mij)>=v[i]){
                val=mij;dr=mij-1;
            }
            else{
                st=mij+1;
            }
        }
        if(val!=-1){
            sol[val]=i;
            update(val,-1);
        }
    }
    for(int i=1;i<=n;i++){
        fout<<sol[i]<<'\n';
    }
    return 0;
}