Cod sursa(job #3180658)

Utilizator TeodorVTeodorV TeodorV Data 5 decembrie 2023 18:41:44
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

const int Nmax=30001;

int v[Nmax],sol[Nmax],n;
int aib[Nmax];

int getp2min(int x)
{
    return (x&(-x));
}

void addAIB(int pos, int val)
{
    while(pos<=n)
    {
        aib[pos]+=val;
        pos+=getp2min(pos);
    }
}

int sumAIB(int pos)
{
    long long rez=0;
    while(pos!=0)
    {
        rez+=aib[pos];
        pos-=getp2min(pos);
    }
    return rez;
}

int getPosMin(int s)
{
    int pas=1<<14,p=0,cs=s;
    while(pas!=0)
    {
        if(p+pas<=n && aib[p+pas]<s)
        {
            s-=aib[p+pas];
            p+=pas;
        }
        pas/=2;
    }
    if(p<n && sumAIB(p+1)==cs)
        return p+1;
    return -1;
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        addAIB(i, 1);
    }
    sol[v[n]]=n;
    addAIB(v[n], -1);
    for(int i=n-1; i>=1; i--)
    {
        int pos=getPosMin(v[i]);
        if(pos==-1)
            pos=v[i];
        addAIB(pos, -1);
        sol[pos]=i;
    }
    for(int i=1; i<=n; i++)
        fout<<sol[i]<<'\n';
    return 0;
}