Cod sursa(job #3267640)

Utilizator TomMMMMatei Toma TomMMM Data 11 ianuarie 2025 17:17:33
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
// met1

#include <iostream>
#include <fstream>
#include <string>

using namespace std;
const string file = "schi";
const int N_max = 30005;

ifstream fin(file + ".in");
ofstream fout(file + ".out");

int n;
int p_inter[N_max];
int p_finale[N_max];

int aint[N_max * 4];


void create(int nod, int st, int dr){
    if(st == dr) {
        aint[nod] = 1;
        return;
    }
    int mid = (st + dr) / 2;
    create(2 * nod, st, mid);
    create(2 * nod + 1, mid + 1, dr);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
int query(int nod, int st, int dr, int k){
    if(st == dr) return st;
    int mid = (st + dr) / 2;
    if(k <= aint[2 * nod])
        return query(2 * nod, st, mid, k);
    else{
        k -= aint[2 * nod];
        return query(2 * nod + 1, mid + 1, dr, k);
    }
}
void update(int nod, int st, int dr, int poz){
    if(st == dr) {
        aint[nod] = 0;
        return;
    }
    int mid = (st + dr) / 2;
    if(poz <= mid)
        update(2 * nod, st, mid, poz);
    else
        update(2 * nod + 1, mid + 1, dr, poz);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> p_inter[i];

    create(1, 1, n);

    for(int i = n; i >= 1; i--){
        int poz = query(1, 1, n, p_inter[i]);
        update(1, 1, n, poz);
        p_finale[poz] = i;
    }
    for(int i = 1; i <= n; i++)
        fout << p_finale[i] << '\n';
}