Cod sursa(job #2908710)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 5 iunie 2022 11:24:04
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb

#import<fstream>
#import<vector>
#import<string>
using namespace std;
int n,cautst,cautdr,val,caut;
vector<int>a,v;
int construire(int nod,int st,int dr)
{
    if(st==dr)
    {
        a[nod]=v[st-1];
    }
    else
    {
        int m=(st+dr)/2;
        a[nod]=construire(nod*2,st,m)+construire(nod*2+1,m+1,dr);
    }
    return a[nod];
}
int query(int nod,int st,int dr,int val)
{
    if(st==dr)
    {
        return st;
    }
    int m=(st+dr)/2;
    if(a[2*nod]<val)
    {
        return query(2*nod+1,m+1,dr,val-a[2*nod]);
    }
    return query(2*nod,st,m,val);
}
int rasp(int val)
{
    return query(1,1,n,val);
}
void update(int nod,int st,int dr)
{
    int mij=(st+dr)/2;
    if(st==dr)
    {
        a[nod]=val;
        return;
    }
    if(caut<=mij)
        update(2*nod,st,mij);
    else
        update(2*nod+1,mij+1,dr);
    a[nod]=a[2*nod]+a[2*nod+1];
}
void upd(int poz,int v)
{
    val=v;
    caut=poz;
    update(1,1,n);
}
ifstream cin("schi.in");
ofstream cout("schi.out");
main()
{
    int q;
    cin>>n;a.resize(4*n+1),v.resize(n);
    for(int i=0;i<n;i++)
    {
        v[i]=1;
    }
    construire(1,1,n);
    for(auto& c:v)
    {
        cin>>c;
    }
    vector<int>rez(n+1,0);
    for(int i=n-1;i>=0;i--)
    {
        int cnt=rasp(v[i]);
        upd(cnt,0);
        rez[cnt]=i+1;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<rez[i]<<' ';
    }
}