Cod sursa(job #2783367)

Utilizator mateitudordmDumitru Matei mateitudordm Data 14 octombrie 2021 12:28:27
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <cmath>
#include <queue>
using namespace std;

int v[30001],aint[130000],w[30001];
void update(int ind,int poz,int st,int dr,int val)
{
    if(st==dr)
        aint[ind]=val;
    else
    {
        if(poz<=(st+dr)/2)
         update(ind*2,poz,st,(st+dr)/2,val);
        else
            update(ind*2+1,poz,(st+dr)/2+1,dr,val);
        aint[ind]=aint[2*ind]+aint[2*ind+1];
    }
}
int query(int ind,int cst,int cdr,int val)
{
    if(cst==cdr)
        return cst;
    if(aint[2*ind]>=val)
        return query(2*ind,cst,(cdr+cst)/2,val);
    else
        return query(2*ind+1,(cst+cdr)/2+1,cdr,val-aint[2*ind]);
}

int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    int n,cn,i;
    cin>>n;
    cn=(1<<int(ceil(double(log2(n)))));
    for(i=1;i<=cn;i++)
      update(1,i,1,cn,1);
    for(i=1;i<=n;i++)
        cin>>v[i];
    for(i=n;i>=1;i--)
    {
       v[i]=query(1,1,cn,v[i]);
       w[v[i]]=i;
       update(1,v[i],1,cn,0);
    }
    for(i=1;i<=n;i++)
        cout<<w[i]<<'\n';
    return 0;
}