Cod sursa(job #729861)

Utilizator hiticas_abelhiticasabel hiticas_abel Data 30 martie 2012 14:39:38
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
using namespace std;
#define lg 30005

int n, i, v[lg], pz, sol[lg], q[65000];
void construieste(int nod, int st, int dr){
    if (st == dr){
        q[nod] = 1;
        return ;
    }
   
    int x = (st+dr) / 2;
   
    construieste(2*nod, st, x);
    construieste(2*nod+1, x+1, dr);
   
    q[nod] = q[2*nod]+q[2*nod+1];
}
int gaseste(int poz, int val, int st, int dr){
    if (st == dr)
        return st;
   
    if (q[2*poz] >= val)
        return gaseste(2*poz, val, st, (st+dr) / 2);
    else
        return gaseste(2*poz+1, val-q[2*poz], (st+dr) / 2+1, dr);
}
void actualizez(int poz, int val, int st, int dr){
    q[poz] --;
    if (st == dr)
        return ;
   
    if (val <= (st+dr) / 2)
        actualizez(2*poz, val, st, (st+dr) / 2);
    else
        actualizez(2*poz+1, val, (st+dr) / 2+1, dr);
}
int main()
{ifstream fin("schi.in");
ofstream fout("schi.out");

    fin>>n;

    for (i = 1; i <= n; i ++)
        fin>>v[i];
   
    construieste(1, 1, n);
   
    for (i = n; i; i --){
        pz = gaseste(1, v[i], 1, n);
       
        sol[pz] = i;
   
       
        actualizez(1, pz, 1, n);
    }
   
    for (i = 1; i <= n; i ++)
        fout<<sol[i]<<"\n";
    fin.close();fout.close();
    return 0;
}