Cod sursa(job #3173597)

Utilizator UengineDavid Enachescu Uengine Data 23 noiembrie 2023 11:57:08
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

const int N = 1 << 15;
int pozitie[N], sol[N];
int logarici, nr_frunze, nr_total;
vector <int> v;

void update(int poz){
    for (int i = poz; i > 0; i /= 2)
        v[i]--;
}

void query(int val_cautare, int poz, int nr_concurent){
    if(val_cautare == 1 and 2 * poz > nr_total){
        sol[poz - nr_frunze + 1] = nr_concurent;
        update(poz);
        return;
    }

    if(val_cautare <= v[2 * poz]){
        query(val_cautare, 2 * poz, nr_concurent);
        return;
    }
    query(val_cautare - v[2 * poz], 2 * poz + 1, nr_concurent);
}

int main() {
    int n;
    cin >> n;
    logarici = log2(n);
    nr_frunze = 1 << logarici;
    if(1 << logarici != n)
        nr_frunze = 1 << (logarici + 1);
    nr_total = nr_frunze * 2 - 1;
    v.resize(nr_total + 1);
    for (int i = 1; i <= nr_total; ++i) {
        v[i] = nr_frunze / (1 << (int)log2(i));
    }
    for (int i = 1; i <= n; ++i)
        cin >> pozitie[i];
    for (int i = n; i > 0; --i) {
        query(pozitie[i], 1, i);
    }
    for (int i = 1; i <= n; ++i) {
        cout << sol[i] << '\n';
    }

    return 0;
}