Cod sursa(job #849957)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 7 ianuarie 2013 21:08:35
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>

#define MAX 30005
#define leftSon (nod << 1)
#define rightSon ((nod << 1) + 1)

using namespace std;

int N, V[MAX], ans[MAX], aInt[MAX << 2];

void init(int nod, int L, int R)
{
    if(L == R) { aInt[nod] = 1; return; }
    int mid = (L + R) >> 1;
    init(leftSon, L, mid);
    init(rightSon, mid + 1, R);
    aInt[nod] = aInt[leftSon] + aInt[rightSon];
}

int find(int nod, int L, int R, int val)
{
    if(L == R) return L;
    int mid = (L + R) >> 1;
    if(aInt[leftSon] >= val) return find(leftSon, L, mid, val);
    else return find(rightSon, mid + 1, R, val - aInt[leftSon]);
}

void mark(int nod, int L, int R, int poz)
{
    if(L == R) { aInt[nod] = 0; return; }
    int mid = (L + R) >> 1;
    if(poz <= mid) mark(leftSon, L, mid, poz);
    else mark(rightSon, mid + 1, R, poz);
    aInt[nod] = aInt[leftSon] + aInt[rightSon];
}

int main()
{
    ifstream in("schi.in"); in>>N; for(int i = 1; i <= N; i++) in>>V[i]; in.close();
    init(1, 1, N);
    for(int i = N; i; i--) { int poz = find(1, 1, N, V[i]); ans[poz] = i; mark(1, 1, N, poz); }
    ofstream out("schi.out"); for(int i = 1; i <= N; i++) out<<ans[i]<<"\n"; out.close();
    return 0;
}