Cod sursa(job #2831551)

Utilizator lolismekAlex Jerpelea lolismek Data 11 ianuarie 2022 17:40:56
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 3e4 + 1, LOGN = 15;
int v[N], rasp[N], n;
vector <int> aib(N);

int lsb(int x){
    return (x & (-x));
}

void update(int poz, int val){
    for(int i = poz; i < aib.size(); i += lsb(i)) aib[i] += val;
}

int query(int poz){
    int ans = 0;
    for(int i = poz; i > 0; i -= lsb(i)) ans += aib[i];
    return ans;
}

int cb(int x){
    int ans = 0, sum = 0;
    for(int pas = (1 << LOGN); pas > 0; pas >>= 1){
        if(ans + pas <= n && sum + aib[ans + pas] < x){
            ans += pas;
            sum += aib[ans];
        }
    }
    return ans + 1;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++) fin >> v[i];
    for(int i = 1; i <= n; i++) update(i, 1);
    for(int i = n; i >= 1; i--){
        int j = cb(v[i]);
        //cout << j << endl;
        rasp[j] = i;
        update(j, -1);
    }
    for(int i = 1; i <= n; i++) fout << rasp[i] << '\n';
    return 0;
}