Cod sursa(job #3240567)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 17 august 2024 11:19:55
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> aint;

void build(int i, int l, int r) {
    if(l == r) {
        aint[i] = 1;
        return;
    }

    int md = (l+r)/2;
    build(2*i, l, md);
    build(2*i+1, md+1, r);

    aint[i] = aint[2*i] + aint[2*i+1];
}

void sub(int i, int l, int r, int p) {
    if(l == r) {
        aint[i] = 0;
        return;
    }

    int md = (l+r)/2;
    if(p <= md) {
        sub(2*i, l, md, p);
    } else {
        sub(2*i+1, md+1, r, p);
    }

    aint[i] = aint[2*i] + aint[2*i+1];
}

int query(int i, int l, int r, int p) {
    if(l == r) {
        return l;
    }


    int md = (l+r)/2;

    if(aint[2*i] >= p) {
        return query(2*i, l, md, p);
    } else {
        return query(2*i+1, md+1, r, p - aint[2*i]);
    }
}

int main() {
    ifstream fin("schi.in");
    ofstream fout("schi.out");

    int N, i, j, cnt;
    fin >> N;
    aint.resize(4*N);
    build(1, 1, N);
    vector<int> locuri(N+1), ocupate(N+1, 0);
    for(i=1; i<=N; ++i) {
        fin >> locuri[i];
    }
    for(i=N; i; --i) {
        cnt = locuri[i]+1;
        j = query(1, 1, N, locuri[i]);
        ocupate[j] = i;
        sub(1, 1, N, j);
    }
    for(i=1; i<=N; ++i) {
        fout << ocupate[i] << ' ' << '\n';
    }
    return 0;
}