Cod sursa(job #3158646)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 19 octombrie 2023 15:23:59
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

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

const int DIM = 30010;

int n;
int v[DIM], aib[DIM], sol[DIM];

int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= (i & -i))
        res += aib[i];
    return res;
}

void update(int x, int val) {
    for (int i = x; i <= n; i += (i & -i))
        aib[i]+=val;
}

int cauta(int x) {
    int st = 1, dr = n, pos = 0;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (query(mid) >= x) {
            pos = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }
    return pos;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++){
        fin >> v[i];
        update(i, 1);
    }

    for (int i = n; i >= 1; i--) {
        int pos = cauta(v[i]);
        sol[pos] = i;
        update(pos, -1);
    }

    for (int i = 1; i <= n; i++)
        fout << sol[i] << '\n';

    return 0;
}