Cod sursa(job #3156461)

Utilizator pctirziuTirziu Petre pctirziu Data 11 octombrie 2023 17:17:43
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#pragma optimize GCC("O3")
using namespace std;
ifstream cin ("schi.in");
ofstream cout ("schi.out");
const int Nmax = 30005;
int v[Nmax], aib[Nmax], sol[Nmax];
int n;
void update(int x)
{
    int i;
    for(i = x; i <= n; i += (i & -i))
        aib[i]++;
}
int solve(int x)
{
    int i, sum = 0;
    for(i = x; i >= 1; i -= (i & -i))
        sum += aib[i];
    return sum;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int i, j;
    cin >> n;
    for(i = 0; i < n; i++)
        cin >> v[i];
    for(i = n - 1; i >= 0; i--){
        int st = 1, dr = n, ans;
        while (st <= dr) {
            int mij = (st + dr) / 2;
            if (mij - solve(mij) >= v[i]) {
              dr = mij - 1;
              ans = mij;
            }
            else
              st = mij + 1;
        }
        sol[ans] = i + 1;
        update(ans);
    }
    for(i = 1; i <= n; i++)
        cout << sol[i] << "\n";
    return 0;
}