Cod sursa(job #1408873)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 30 martie 2015 12:01:05
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
vector<short> tree,a,sol;
short n,val,pos;
void build(short x,short left,short right)
{
    if(left==right)
        tree[x]=1;
    else{
        short 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(short x,short left,short right)
{
    if(left==right)
    {
        pos=left;
        tree[x]--;
    }
    else{
        short 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;
    tree=vector<short> (4*n+1);
    sol=a=vector<short> (n+1);
    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;
}