Cod sursa(job #2909317)

Utilizator MafteiAlbertAlexandruMaftei Albert-Alexandru MafteiAlbertAlexandru Data 12 iunie 2022 18:05:56
Problema Schi Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
unsigned int n, n2;//65536
int arbint[400];
void update(int p, int stnod, int drnod, int i)
{
    if(i>=n2)
    {
        arbint[i]=0;
        return;
    }
    arbint[i]--;
    int mij =(stnod+drnod)/2;
    if(p>mij)
    {
        update(p,mij, drnod, i*2+1);
    }
    else update(p,stnod,mij,i*2);
}

int cb(int v)
{
    int index=1;
    while(v>=1&&index<n2)
    {
        if(arbint[index*2]<v)
        {
            v-=arbint[index*2];
            index=index*2+1;
        }else {
            index=index*2;
        }
    }
    return index-n2+1;
}
int in[30005];
int out[30005];
int main()
{
    f>>n;
    n2=(1<<(31 - __builtin_clz(n)));
    if(n2<n)n2 = (n2 << 1);

    for(int i=n2;i<n2+n;i++)
    {
        arbint[i]=1;
    }
    for(int i=n2/2; i>0; i=i/2)
    {
        for(int j=i; j<2*i;j++)
        {
            arbint[j]=arbint[j*2]+arbint[j*2+1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        f>>in[i];
    }
    for(int i=n;i>0;i--)
    {
        int p =cb(in[i]);
        out[p]=i;
        update(p,1,n2,1);
    }
    for(int i=1;i<=n;i++)
        g<<out[i]<<'\n';
    return 0;
}