Cod sursa(job #2953129)

Utilizator aronaronBartha Aron aronaron Data 10 decembrie 2022 15:30:55
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin ("schi.in");
ofstream cout ("schi.out");

/// Boilerplate
struct AIB {
    vector<int> buf;
    AIB (int n) {
        buf.resize(n /*+1*/);
    }
    int Quiry (int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) {
            s += buf[i];
        }
        return s;
    }
    /// Smecherie (BS)
    int Search (int x) {
        int ret = -1;
        int l = 1, m, r = buf.size() /*-1*/;
        while (l <= r) {
            m = (l + r) >> 1;
            if (Quiry(m) >= x) r = (ret = m) - 1;
            else l = m + 1;
        }
        return ret;
    }
    void Update (int i, int x) {
        for (; i < buf.size(); i += i & -i)
            buf[i] += x;
    }
};


const int Dim = 30001;

int n;
vector<int> rez(Dim);
AIB aib(Dim);
void Rezolva (int i = 1) {
    if (i > n) return;
    int x;
    /// Stage 1. (CITIRE):
    ///    i: 1 .. n
    aib.Update(i, 1); // Fill with 1
    cin >> x;
    Rezolva(i + 1); // BOOM!
    /// Stage 2. (CALCULE):
    ///    i: n .. 1
    int pos = aib.Search(x);
    rez[pos] = i;
    aib.Update(pos, -1);
}

int main(){
    cin >> n;
    Rezolva();
    for (int i = 1; i <= n; ++i)
        cout << rez[i] << '\n';
    return 0;
}