Cod sursa(job #3158690)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 19 octombrie 2023 17:27:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("schi.in");
ofstream cout("schi.out");
const int NMAX = 30005;
int n;
vector<int> aint(4 * NMAX);
void build(int nod, int l, int r){
    aint[nod] = r - l + 1;

    if(l == r)
        return;
    
    const int mid = (l + r) / 2;
    build(2 * nod, l, mid);
    build(2 * nod + 1, mid+1, r);
}
int update(int nod, int l, int r, int pos){
    aint[nod]--;

    if(l == r){
        return l;
    }
    const int mid = (l + r) / 2;

    if(pos <= aint[2 * nod])
        return update(2 * nod, l, mid, pos);
    
    return update(2 * nod + 1, mid+1, r, pos - aint[2 * nod]);
}
int main(){
    cin>>n;
    build(1, 1, n);

    vector<int> updates(n+1), output(n+1);
    for(int i=1; i<=n; i++)
        cin>>updates[i];
    
    for(int i=n; i>=1; i--){
        const int pos = update(1, 1, n, updates[i]);
        output[pos] = i;
    }

    for(int i=1; i<=n; i++)
        cout<<output[i]<<"\n";

    return 0;
}