Cod sursa(job #2273335)

Utilizator vescaDamian-Teodor BELES vesca Data 31 octombrie 2018 13:48:44
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>

#define LSB(x) (x & (-x))
#define cin fin
#define cout fout

using namespace std;

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

int N;
vector<int> input, output;

struct FenwickTree {
    vector<int> ft;
    int ft_size;

    FenwickTree(int n) {
        ft.resize(n, 0);
        ft_size = n;
    }

    int rsq(int x) {
        int sum = 0;
        for (; x; x -= LSB(x)) sum += ft[x];
        return sum;
    }

    void adjust(int k, int v) {
        for (; k < ft_size; k += LSB(k)) ft[k] += v;
    }
};

void Read() {
    cin >> N;
    input.resize(N + 1);
    output.resize(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> input[i];
}

int lower_bound(FenwickTree &ft, int v) {
    int left = 1, right = ft.ft_size;

    while (left <= right) {
        int middle = (left + right) / 2;

        int middle_rsq = ft.rsq(middle);

        if (middle_rsq < v)
            left = middle + 1;
        else right = middle - 1;
    }

    return left;
}

void Solve() {
    FenwickTree ft(N + 1);

    for (int i = 1; i <= N; ++i) {
        ft.adjust(i, 1);
    }

    for (int i = N; i >= 1; --i) {
        int current_place = lower_bound(ft, input[i]);
        output[current_place] = i;
        ft.adjust(current_place, -1);
    }
}

void Print() {
    for (int i = 1; i <= N; ++i)
        cout << output[i] << "\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}