Cod sursa(job #1408902)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 30 martie 2015 12:19:24
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define nmax 30001
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int n,val,pos,tree[4*nmax],a[nmax],sol[nmax];
void build(int x,int left,int right)
{
    if(left==right)tree[x]=1;
    else{
        int mid=(left+right)/2;
        build(2*x,left,mid);
        build(2*x+1,mid+1,right);
        tree[x]=tree[2*x]+tree[2*x+1];
    }
}
void query(int x,int left,int right)
{
    if(left==right)
    {
        pos=left;
        tree[x]--;
    }
    else{
        int mid=(left+right)/2;
        if(tree[2*x]>=val)query(2*x,left,mid);
        else{
            val-=tree[2*x];
            query(2*x+1,mid+1,right);
        }
        tree[x]=tree[2*x]+tree[2*x+1];
    }
}
int main()
{
    in>>n;
    build(1,1,n);
    for(int i=1;i<=n;i++)in>>a[i];
    for(int i=n;i>0;i--)
    {
        val=a[i];
        query(1,1,n);
        sol[pos]=i;
    }
    for(int i=1;i<=n;i++)
        out<<sol[i]<<'\n';
    return 0;
}