Cod sursa(job #3156829)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 13 octombrie 2023 13:02:58
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif

using namespace std;
#ifndef LOCAL
ifstream in("schi.in");
ofstream out("schi.out");
#endif
const int nmax = 30005;

struct aint
{
    int nxtp2(int n)
    {
        int p=1;
        while(p<n)p*=2;
        return p;
    }
    int offset;
    int *data;
    aint(int n)
    {
        offset=nxtp2(n);
        data=new int[offset*2];
        for(int i=0;i<offset*2;i++)data[i]=0;
        init(0,offset-1,1);
    }
    void init(int st,int dr,int node)
    {
        if(st==dr)
        {
            data[node]=1;
            return;
        }
        int mid=(st+dr)/2;
        init(st,mid,node*2);
        init(mid+1,dr,node*2+1);
        data[node]=data[node*2]+data[node*2+1];
    }
    void update(int poz)
    {
        data[offset+poz]=0;
        for(poz=(poz+offset)/2;poz>0;poz/=2)data[poz]=data[poz*2]+data[poz*2+1];
    }
    int _cb(int l,int x,int &sum,int st,int dr,int node)
    {
        if(dr<l)return dr;
        if(l<=st&&data[node]+sum<x)
        {
            sum+=data[node];
            return dr;
        }
        if(st==dr)return st-1;
        int mij=(st+dr)/2;
        int ras=_cb(l,x,sum,st,mij,node*2);
        if(ras<mij)return ras;
        if(ras==mij)return _cb(l,x,sum,mij+1,dr,node*2+1);
        return 0;
    }
    int cb(int x)
    {
        int sum=0;
        return _cb(0,x,sum,0,offset-1,1);
    }
    void debug()
    {
        cerr<<data[1]<<'\n';
        cerr<<data[2]<<' '<<data[3]<<'\n';
        cerr<<data[4]<<' '<<data[5]<<' '<<data[6]<<' '<<data[7]<<'\n';
        cerr<<data[8]<<' '<<data[9]<<' '<<data[10]<<' '<<data[11]<<' '<<data[12]<<' '<<data[13]<<' '<<data[14]<<' '<<data[15]<<'\n';
    }
};

int ans[nmax];

int main()
{
    int n;in>>n;
    aint root=aint(n);
    vector<int> v;
    for(int i=0;i<n;i++)
    {
        int nr;in>>nr;
        v.push_back(nr);
    }
    for(int i=n-1;i>=0;i--)
    {
        //cerr<<v[i]<<"->";
        int rez = root.cb(v[i]);
        rez++;
        //cerr<<rez<<'\n';
        root.update(rez);
        //root.debug();
        ans[rez+1]=i+1;
    }
    for(int i=1;i<=n;i++)
    {
        out<<ans[i]<<'\n';
    }
}