Cod sursa(job #1462616)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 18 iulie 2015 16:39:24
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int NMAX = 30005;

struct ARB{

    short int poz;
    short int sum;
};
ARB arb[4 * NMAX];

short int N,v[NMAX],a[NMAX];

void read()
{

    in>>N;
    for(short int i = 1; i <= N ; ++i)
        in>>v[i];
    in.close();
}

void update(short int nod,short int left,short int right,short int val,short int poz)
{

    if(left == right){

        arb[nod].poz = poz;
        arb[nod].sum = val;
        return;
    }
    short int mid = (left + right) >> 1;
    if(mid >= poz)
        update(2 * nod,left,mid,val,poz);
    else
        update(2 * nod + 1,mid + 1,right,val,poz);
    arb[nod].sum = arb[2 * nod].sum + arb[2 * nod + 1].sum;
    if(arb[2 * nod + 1].sum == 0)
        arb[nod].poz = arb[2 * nod].poz;
    else
        arb[nod].poz = arb[2 * nod + 1].poz;
}

short int query(short int nod,short int left,short int right,short int suma)
{

    if(arb[nod].sum == suma)
        return arb[nod].poz;
    short int mid = (left + right) >> 1;
    if(arb[2 * nod].sum >= suma)
        return query(2 * nod,left,mid,suma);
    else
        return query(2 * nod + 1,mid + 1,right,suma - arb[2 * nod].sum);

}

int main()
{

    read();
    for(short int i = 1 ; i <= N ; ++i)
        update(1,1,N,1,i);
    for(short int i = N ; i >= 1 ; --i){

        short int sol = query(1,1,N,v[i]);
        a[sol] = i;
        update(1,1,N,0,sol);
    }
    for(short int i = 1 ; i <= N ; ++i)
        out<<a[i]<<"\n";
    return 0;
}