Cod sursa(job #3159018)

Utilizator radu._.21Radu Pelea radu._.21 Data 20 octombrie 2023 14:39:38
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>


using namespace std;
int n,sol[30001],v[30001],aib[30001];
ifstream fin("schi.in");
ofstream fout("schi.out");
int query(int poz){
    int s=0;
    for(int i=poz;i>=1;i-=(i&(-i)))
        s+=aib[i];
    return s;
}
void update(int poz,int val){
    for(int i=poz;i<=n;i+=(i&(-i))){
        aib[i]+=val;
    }
}

int cb(int val){
    int st=1,dr=n,pozmax=0;
    while(st<=dr){
        int mid=(st+dr)/2;
        if(query(mid)>=val)
            dr=mid-1,pozmax=mid;
        else st=mid+1;
    }
    return pozmax;
}
int main(){
    fin>>n;
    for(int i=1;i<=n;i++)
            fin>>v[i];
   for(int i=1;i<=n;i++)
        update(i,1);
    for(int i=n;i>=1;i--){
        int val=v[i];
        /// caut cea mai din stanga val din s
        int poz=cb(val);
        sol[poz]=i;
        update(poz,-1);
    }
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<'\n';
    return 0;
}