Cod sursa(job #2543715)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 11 februarie 2020 14:17:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>
#define nmax 30000

using namespace std;

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

int arb[4*nmax],v[nmax+2];
int fr[nmax+2],val[nmax+2];
int n;
//-------------------------------------------------
void update(int st, int dr, int nod, int pos)
{
    if(st==dr)
    {
        arb[nod]=fr[pos];
    }
    else
    {
        int mij=(st+dr)/2;
        if(pos<=mij) update(st,mij,2*nod,pos);
        else update(mij+1,dr,2*nod+1,pos);

        arb[nod]=arb[nod*2]+arb[nod*2+1];
    }
}
//-------------------------------------------------
int query(int st, int dr, int nod, int res)
{
    if(st==dr)
    {
        return st;
    }
    else
    {
        int mij=(st+dr)/2;
        if(arb[2*nod]<res) return query(mij+1, dr, 2*nod+1, res-arb[2*nod]);
        else return query(st, mij, 2*nod, res);
    }
}
//-------------------------------------------------
int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        fr[i]=1;
        update(1,n,1,i);
    }
    for(int i=n; i>0; i--)
    {
        int sol=query(1,n,1,v[i]);
        fr[sol]=0;
        update(1,n,1,sol);
        val[sol]=i;
    }
    for(int i=1; i<=n; i++)
    {
        fout<<val[i]<<"\n";
    }
    return 0;
}