Cod sursa(job #2765445)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 26 iulie 2021 21:20:59
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <iostream>

using namespace std;

const int MAX_N = 30000;

int vec[MAX_N];
int aib[MAX_N + 1];
int nrnr;

int query(int pos) {
    int ans;
    ans = 0;
    while (pos) {
        ans += aib[pos];
        pos = pos & (pos - 1);
    }
    return ans;
}

void addval(int val, int pos) {
    while (pos <= nrnr) {
        aib[pos] += val;
        pos += pos & -pos;
    }
}

int setpos(int val) {
    int sav;
    int ans;
    sav = 0;
    ans = 0;
    for (int index = (1 << 20); index; index >>= 1) {
        if (ans + index <= nrnr && sav + aib[ans + index] < val) {
            ans += index;
            sav += aib[ans];
        }
    }
    ans++;
    addval(-1, ans);
    return ans;
}

int ans[MAX_N];

int main()
{
    std::ifstream fin("schi.in");
    std::ofstream fout("schi.out");
    fin >> nrnr;
    for (int index = 1; index <= nrnr; index++) {
        aib[index] = index & -index;
    }
    for (int index = 0; index < nrnr; index++) {
        fin >> vec[index];
    }
    for (int index = nrnr - 1; index >= 0; index--) {
        ans[setpos(vec[index]) - 1] = index;
    }
    for (int index = 0; index < nrnr; index++) {
        fout << ans[index] << '\n';
    }
}