Cod sursa(job #2619234)

Utilizator danielsociuSociu Daniel danielsociu Data 27 mai 2020 12:19:54
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
#define ST          first
#define ND          second
#define PB          push_back
#define MKP         make_pair
#define LWBND		lower_bound
#define UPBND		upper_bound
#define FOR(i,a,b)  for(int i=(a);i<=(b);++i)
#define FORS(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x)      x.begin(),x.end()
#define SZ(x)       ((int)(x).size())
#define MOD         1000000007 //998244353
#define MAXN        30005
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int INF=0x3f3f3f3f;

int n,poz;
int v[MAXN],aint[4*MAXN],sol[MAXN];

void generator(int node,int val){
    aint[node]=val;
    if(val==1)
        return;
    generator(node*2,val/2);
    if(val&1)
        generator(node*2+1,val/2+1);
    else
        generator(node*2+1,val/2);
}

int solver(int node,int st, int dr,int val){
    aint[node]--;
    if(st==dr)
        return st;
    int middle = (st+dr-1)/2;
    if(aint[node*2]>=val)
        return solver(node*2,st,middle,val);
    else{
        val -= aint[node*2];
        return solver(node*2+1,middle+1,dr,val);
    }
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    cin>>n;
    FOR(i,1,n) cin>>v[i];
    generator(1,n);
    for(int i=n;i>0;--i){
        poz = solver(1,1,n,v[i]);
        sol[poz]=i;
    }
    FOR(i,1,n)
        cout<<sol[i]<<'\n';

}