Cod sursa(job #2830198)

Utilizator gapdanPopescu George gapdan Data 9 ianuarie 2022 17:07:42
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <vector>

const int MAX_SIZE = 100005;
const int MAX_TREE_SIZE = 1000006;
int v[MAX_SIZE];
int score[MAX_SIZE];
int aint[MAX_TREE_SIZE];

int get_elem(int left, int right, int elem, int index) {
    int crtVal, pozLeft, pozRight, mid;
    int leftVal, rightVal;
    if (right <= left) {
        aint[index]++;
        return left;
    }

    crtVal = (right - left + 1) - aint[index];
    pozLeft = index * 2;
    pozRight = index * 2 + 1;
    mid = (right + left) / 2;
    leftVal = (mid - left + 1) - aint[pozLeft];
    rightVal = (right - mid) - aint[pozRight];
    if (leftVal >= elem) {
        int sol = get_elem(left, mid, elem, pozLeft);
        ++aint[index];
        return sol;
    } else if (leftVal + rightVal >= elem) {
        elem -= leftVal;
        int sol = get_elem(mid + 1, right, elem, pozRight);
        ++aint[index];
        return sol;
    }
    return -1;
}

int main() {
    int n;
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &v[i]);
    }

    for (int i = n; i >= 1; --i) {
        int poz = get_elem(1, n, v[i], 1);
        score[poz] = i;
    }

    for (int i = 1; i <= n; ++i) {
        printf("%d\n", score[i]);       
    }
    return 0;
}