Cod sursa(job #3247727)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 8 octombrie 2024 21:52:46
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <iostream>
using namespace std;
int v[66000], nr[30005], r[30005];
void modif(int nod, int a, int b, int poz, int x) {
    int mij = (a + b) / 2;
    if (a == poz && b == poz) {
        v[nod] += x;
    }
    else {
        if (poz <= mij) {
            modif(nod * 2, a, mij, poz, x);
        }
        else {
            modif(nod * 2 + 1, mij + 1, b, poz, x);
        }
        v[nod] = v[nod * 2] + v[nod * 2 + 1];
    }
}
int sum(int nod, int a, int b, int x, int y) {
    int mij = (a + b) / 2, r;
    if (x <= a && b <= y) {
        return v[nod];
    }
    r = 0;
    if (x <= mij) {
        r += sum(nod * 2, a, mij, x, y);
    }
    if (y > mij) {
        r += sum(nod * 2 + 1, mij + 1, b, x, y);
    }
    return r;
}
int main() {
    int n, i, st, dr, mij;
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin >> n;
    for (i = 0; i < n; i++) {
        fin >> nr[i];
    }
    for (i = n - 1; i >= 0; i--) {
        st = 0;
        dr = n;
        while (dr - st > 1) {
            mij = (st + dr) / 2;
            //cout << i << ' ' << nr[i] << ' ' << mij << ' ' << sum(1, 1, n, 1, mij) << '\n';
            if (mij - sum(1, 1, n, 1, mij) < nr[i]) {
                st = mij;
            }
            else {
                dr = mij;
            }
        }
        r[dr] = i + 1;
        modif(1, 1, n, dr, 1);
        //cout << dr << '\n';
        //break;
    }
    for (i = 1; i <= n; i++) {
        fout << r[i] << '\n';
    }
    return 0;
}