Cod sursa(job #856580)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 16 ianuarie 2013 19:01:15
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
//le varianta cu AINT

#include <iostream>
#include <fstream>

using namespace std;

ifstream in ("schi.in");
ofstream out ("schi.out");

int N;
int AINT[(1 << 15) + 5];
int Poz[30010], Sol[30010];

void Update (int nod, int st, int dr, int poz, int val)
{
    if (st == dr){
        AINT[nod] = val;
        return;
    }

    int mid = (st + dr) >> 1;

    if (poz <= mid)
        Update (nod << 1, st, mid, poz, val);
    else
        Update (nod << 1 | 1, mid + 1, dr, poz, val);

    AINT[nod] = AINT[nod << 1] + AINT[nod << 1 | 1];
}

int Query (int nod, int st, int dr, int val)
{
    if (st == dr)
        return st;

    int mid = (st + dr) >> 1;

    if (val <= AINT[nod << 1])
        return Query (nod << 1, st, mid, val);
    else
        return Query (nod << 1 | 1, mid + 1, dr, val - AINT[nod << 1]);
}

int main ()
{
    int i, now;

    in >> N;

    for (i = 1; i <= N; i ++){
        in >> Poz[i];
        Update (1, 1, N, i, 1);
    }

    for (i = N; i; i --){
        now = Query (1, 1, N, Poz[i]);
        Sol[now] = i;
        Update (1, 1, N, now, 0);
    }

    for (i = 1; i <= N; i ++)
        out << Sol[i] << "\n";

    return 0;
}