Cod sursa(job #2860997)

Utilizator PescaPescariu Matei Alexandru Pesca Data 3 martie 2022 12:12:24
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int const N=3*(int)1e5+5;
int n,in[N],aint[4*N],x,rez[N];
void build(int p=1,int l=1,int r=x)
{
    if(l==r)
    {
        aint[p]=1;
        return;
    }
    int m=(l+r)/2;
    build(p*2,l,m);
    build(p*2+1,m+1,r);
    aint[p]=aint[p*2]+aint[p*2+1];
}
void upd(int conc,int poz,int nod=1)
{
    if(poz>aint[nod])poz-=aint[nod],nod++;
    aint[nod]--;
    if(nod>=x)
        {rez[nod-x]=conc;return;}
    upd(conc,poz,nod*2);
}
void a()
{
    for(int i=1;i<16;i++)
        cout<<aint[i]<<' ';
    cout<<'\n';
}
int main()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>in[i];
    for(x=1;x<n;x=(x<<1));
    ///cout<<x<<' '<<n;
    build();
    for(int i=n-1;i>-1;i--)
        upd(i,in[i]);
    for(int i=0;i<n;i++)
        fout<<rez[i]+1<<'\n';
}