Cod sursa(job #3141328)

Utilizator tmi26Teodor Stupariu tmi26 Data 13 iulie 2023 17:38:34
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
const int cst=3*1e4;
int v[cst+5],rez[cst+5],aint[4*cst+5],n;
void act(int nod,int l,int r,int val)
{
    if(l==r)
        aint[nod]++;
    else
    {
        int mij=(l+r)/2;
        if(val<=mij)
            act(2*nod,l,mij,val);
        else
            act(2*nod+1,mij+1,r,val);
        aint[nod]=aint[nod*2]+aint[nod*2+1];
    }
}
int calcul(int nod,int l,int r,int s,int d)
{
    if(s<=l&&r<=d)
    {
        return aint[nod];
    }
    else
    {
        int mij=(l+r)/2,sol=0;
        if(s<=mij)
            sol+=calcul(2*nod,l,mij,s,d);
        if(d>mij)
            sol+=calcul(2*nod+1,mij+1,r,s,d);
        return sol;
    }
}
int calc(int poz)
{
    int i1=1,i2=n,mij,rez;
    while(i1<=i2)
    {
        mij=(i1+i2)/2;
        int val;
        if(mij!=1)
            val=calcul(1,1,n,1,mij-1);
        else val=0;
        if(mij-val>poz)
            i2=mij-1;
        else
        {
            rez=mij;
            i1=mij+1;
        }
    }
    return rez;
}
int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    for(int i=n; i>=1; i--)
    {
        int pozn=calc(v[i]);
        act(1,1,n,pozn);
        rez[pozn]=i;
    }
    for(int i=1; i<=n; i++)
        fout<<rez[i]<<'\n';
    return 0;
}