Cod sursa(job #3311839)

Utilizator TeogaloiuTeodor Galoiu Teogaloiu Data 24 septembrie 2025 15:40:29
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <cmath>
using namespace std;
ifstream cin ("schi.in");
ofstream cout ("schi.out");
const int Size=300001;
int v[Size];
int dp[4*Size];
int position;
int res[Size];
void buildTree(int pos,int st,int dr)
{
    if(st==dr){
        dp[pos]=1;
        return;
    }
    int mij=(st+dr)/2;
    buildTree(pos*2,st,mij);
    buildTree(pos*2+1,mij+1,dr);
    dp[pos]=dp[pos*2]+dp[pos*2+1];
}

void Search(int Node,int st, int dr,int s )
{
    if(st==dr)
    {
        position=Node;
        dp[Node]=0;
        return;
    }
    int mij=(st+dr)/2;
    if(s>dp[2*Node])
        Search(2*Node+1,st,mij,s-dp[2*Node]);
    else
        Search(2*Node,mij+1,dr,s);
        
    dp[Node]=dp[Node*2]+dp[Node*2+1];
}
int main()
{
    int n;
    cin>>n;
    int Power=log2(n);
    Power+=((1<<Power)<n);
    Power=(1<<Power);
    buildTree(1,1,Power);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
//    for(int i=1;i<=2*Power;i++)
//        cout<<dp[i]<<' ';

    for(int i=n;i>=1;i--)
    {
        Search(1,1,Power,v[i]);
        res[position-Power+1]=i;
       // cout<<"true pos: "<<position<<" in rez pos: "<<position-Power<<'\n';
    }
    for(int i=1;i<=n;i++)
        cout<<res[i]<<'\n';
    return 0;
}