Cod sursa(job #2755798)

Utilizator deliabaltatescuBaltatescu Delia Elena deliabaltatescu Data 28 mai 2021 10:36:52
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>

using namespace std;

const int nMax = 30005;

int a[nMax], rez[nMax], v[100000], indexVal;

void construieste(int pozNod, int indexSt, int indexDr) {
    if (indexSt == indexDr) {
        v[pozNod] = 1;
        return;
    }

    int indexMij = (indexSt + indexDr) / 2;
    if (indexVal <= indexMij) {
        construieste(2 * pozNod, indexSt, indexMij);
    } else {
        construieste(2 * pozNod + 1, indexMij + 1, indexDr);
    }

    v[pozNod] = v[2 * pozNod] + v[2 * pozNod + 1];
}

int cautaApoiStergeElementulNrK(int pozNod, int indexSt, int indexDr, int k) {
    if (indexSt == indexDr) {
        v[pozNod] = 0;
        return indexSt;
    }

    int indexMij = (indexSt + indexDr) / 2, indexGasit;
    if (k <= v[2 * pozNod]) {
        indexGasit = cautaApoiStergeElementulNrK(2 * pozNod, indexSt, indexMij, k);
    } else {
        indexGasit = cautaApoiStergeElementulNrK(2 * pozNod + 1, indexMij + 1, indexDr, k - v[2 * pozNod]);
    }

    v[pozNod] = v[2 * pozNod] + v[2 * pozNod + 1];
    return indexGasit;
}

int main() {
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    int n;

    cin >> n;
    for (indexVal = 1; indexVal <= n; indexVal++) {
        cin >> a[indexVal];
        construieste(1, 1, n);
    }

    for (int i = n; i >= 1; i--) {
        int pozitiaK = cautaApoiStergeElementulNrK(1, 1, n, a[i]);
        rez[pozitiaK] = i;
    }

    for (int i = 1; i <= n; i++) {
        cout << rez[i] << "\n";
    }
}