Cod sursa(job #3158644)

Utilizator Utucora2017Nicolae Utucora2017 Data 19 octombrie 2023 15:22:21
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<fstream>
using namespace std;
ifstream cin("schi.in");
ofstream cout("schi.out");
int n, a[30005];
int aib[30005];
int sol[30005];
void update(int poz, int val){
    for(int i=poz;i<=n;i=i+(i&(-i)))
        aib[i]+=val;

}
int query(int poz){
    int s=0;
    for(int i=poz;i>=1;i-=i&(-i))
        s+=aib[i];
    return s;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        update(i,1);
    }
    for(int i=n;i>=1;i--){
        int x=a[i],st=1,dr=n,poz=0;
        while(st<=dr){
            int mid=(st+dr)/2;
            if(query(mid)>=x){
                poz=mid;
                dr=mid-1;
            }
            else
                st=mid+1;
        }
        sol[poz]=i;
        update(poz,-1);
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<"\n";
}