Cod sursa(job #2784101)

Utilizator DragosC1Dragos DragosC1 Data 15 octombrie 2021 19:10:25
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
using namespace std;

int n;
int a[30001], b[30001];
int aib[30001];

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

int range(int x) {
    int i, sum = 0;
    for (i = x; i > 0; i -= i & -i)
        sum += aib[i];
    return sum;
}

void read() {
    int i;
    ifstream f("schi.in");
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];
    f.close();
}

void solve() {
    int i, st, dr, mij;
    for (i = 1; i <= n; i++)
        add(i, 1);
    for (i = n; i >= 1; i--) {
        st = 1, dr = n;
        while (st <= dr) {
            mij = (st + dr) / 2;
            if (range(mij) >= a[i])
                dr = mij - 1;
            else st = mij + 1;
        }
        b[st] = i;
        add(st, -1);
    }
}

void output() {
    ofstream g("schi.out");
    for (int i = 1; i <= n; i++)
        g << b[i] << '\n';
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}