Cod sursa(job #2302123)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 13 decembrie 2018 20:27:41
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#define dim 30001
using namespace std;

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

int AIB[dim];
int N, A[dim], B[dim], i, step, pos;

void Update(int poz, int val) {
    while (poz <= N) {
        AIB[poz] += val;
        poz = poz + (poz & (-poz));
    }
}

int Querry(int x, int step) { // pentru ca log^2 de la AIB e mai bun decat log de la aint, hai sa vedem ce face log la AIB
    int sol = 0;
    while (step) {
        if (AIB[step + sol] < x) {
            x -= AIB[step + sol];
            sol += step;
        }
        step >>= 1;
    }
    return sol + 1;
}
int main() {
    f >> N;
    for (i = 1; i <= N; ++i) {
        Update(i, 1); //am un spatiu liber pe intervalul i,i
        f >> A[i];
    }
    step = 1;
    while (step <= N) step <<= 1;
    step >>= 1;
    for (i = N; i >= 1; --i) {
        pos = Querry(A[i], step);
        Update(pos, -1);
        B[pos] = i;
    }
    for (i = 1; i <= N; ++i)
        g << B[i] << '\n';
}