Cod sursa(job #2758552)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 10 iunie 2021 23:02:24
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

using namespace std;

const int N = 30000;
const int P2MAX = (1 << 16);

int loc[N + 1], aint[P2MAX], rez[N + 1], val, poz;

void actualizare(int p, int st, int dr) {
    if (st == dr) {
        aint[p] += val;
        return;
    }
    int m = (st + dr) / 2;
    if (poz <= m)
        actualizare(2 * p, st, m);
    else
        actualizare(2 * p + 1, m + 1, dr);
    aint[p] = aint[2 * p] + aint[2 * p + 1];
}

int caut(int s, int p, int st, int dr) {
    if (st == dr)
        return dr;
    int m = (st + dr) / 2;
    if (s > aint[2 * p])
        return caut(s - aint[2 * p], 2 * p + 1, m + 1, dr);
    return caut(s, 2 * p, st, m);
}

int main() {
    ifstream in("schi.in");
    ofstream out("schi.out");
    int n;
    in >> n;
    for (int i = 1; i <= n; ++i) {
        in >> loc[i];
        val = 1, poz = i;
        actualizare(1, 1, n);
    }
    in.close();
    for (int i = n; i >= 1; --i) {
        poz = caut(loc[i], 1, 1, n);
        rez[poz] = i;
        val = -1;
        actualizare(1, 1, n);
    }
    for (int i = 1; i <= n; ++i)
        out << rez[i] << '\n';
    out.close();
    return 0;
}