Cod sursa(job #2901909)

Utilizator RaduAntoneoAntonio Alexandru Radu RaduAntoneo Data 14 mai 2022 19:34:57
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");
#define cin f
#define cout g

int cls_inter[30001], aInt[120000], cls_final[30001];
 
void build(int nod, int st, int dr) {
    if(st == dr) {
        aInt[nod] = cls_inter[st];
        return;
    }
    int mij = (st + dr) / 2;
    build(nod * 2, st, mij);
    build(nod * 2 + 1, mij + 1, dr);
    aInt[nod] = aInt[nod * 2] + aInt[nod * 2 + 1];
}
 
void modif(int nod, int st, int dr, int i, int val) {
    if(i < st || i > dr) return;
    if(st == dr) {
        aInt[nod] = val;
        return;
    }
    modif(nod * 2, st, (st + dr) / 2, i, val);
    modif(nod * 2 + 1, (st + dr) / 2 + 1, dr, i, val);
    aInt[nod] = aInt[nod * 2] + aInt[nod * 2 + 1];
}
 
int fixare(int nod, int st, int dr, int poz_inter) {
    if(st == dr) return st;
    if(aInt[2 * nod] < poz_inter)
        return fixare(nod * 2 + 1, (st + dr) / 2 + 1, dr, poz_inter - aInt[nod * 2]);
    return fixare(nod * 2, st, (st + dr) / 2, poz_inter);
}

int main() {
    int n, i, p;
    cin >> n;
    for(i = 1; i <= n; i++)
        cls_inter[i] = 1;

    build(1, 1, n);
    for(i = 1; i <= n; i++)
        cin >> cls_inter[i];
    
    for(i = n; i >= 1; i--) {
        p = fixare(1, 1, n, cls_inter[i]);
        cls_final[p]=i;
        modif(1, 1, n, p, 0);
    }
    for(i = 1; i <= n; i++)
        cout << cls_final[i] << '\n';
}