Cod sursa(job #3312663)

Utilizator RaduCalisovCalisovRadu RaduCalisov Data 29 septembrie 2025 13:01:06
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
vector<int> arb;
vector<int> res;

void create(int st,int dr,int pos){
    if(st==dr)
        arb[pos] = 1;
    else{
        int mij = (st+dr)/2;
        int c1 = pos * 2;
        int c2 = pos * 2 + 1;

        create(st,mij,c1);
        create(mij+1,dr,c2);

        arb[pos] = arb[c1]+arb[c2];
    }
}

void upd(int st,int dr,int pos,int id){
    if(st==dr)
        arb[pos] = 0;
    else{
        int mij = (st+dr)/2;
        int c1 = pos * 2;
        int c2 = pos * 2 + 1;

        if(mij>=id)
            upd(st,mij,c1,id);
        if(mij+1<=id)
            upd(mij+1,dr,c2,id);

        arb[pos] = arb[c1]+arb[c2];
    }    
}

int find(int st,int dr,int pos,int sum){
    if(st==dr)
        return st;
    else{
        int mij = (st+dr)/2;
        int c1 = pos * 2;
        int c2 = pos * 2 + 1;

        if(arb[c1]>=sum)
            return find(st,mij,c1,sum);
        else
            return find(mij+1,dr,c2,sum-arb[c1]);


    }
}

int main() {
    ifstream cin("schi.in");
    ofstream cout("schi.out");

    int n;
    cin>>n;
    v.resize(n+1);
    arb.resize(n*4);
    res.resize(n+1);

    for(int i=1;i<=n;i++)
    cin>>v[i];

    create(1,n,1);

    for(int i=n;i>0;i--){
        int pos = find(1,n,1,v[i]);
        upd(1,n,1,pos);
        res[pos] = i;
    }
    for(int i=1;i<=n;i++)
        cout<<res[i]<<"\n";
}