Cod sursa(job #3133840)

Utilizator sara_ionescu21Ionescu Sara sara_ionescu21 Data 27 mai 2023 01:49:14
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[100001], a[100001], rez[100001];
int n;

int q(int p)
{
    int suma = 0;

    for (int i = p; i; i -= i & -i)
        suma += a[i];

    return suma;
}

int cb(int p)
{
    int l = 1, r = n, pos = n;

    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (q(mid) >= p)
        {
            r = mid - 1;
            pos = mid;
        }
        else
            l = mid + 1;
    }

    return pos;
}

void upd(int p, int x)
{
    for (int i = p; i <= n; i += i & -i)
        a[i] += x;
}

int main()
{
    fin >> n;

    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        upd(i, 1);
    }

    for (int i = n; i >= 1; --i)
    {
        int p = cb(v[i]);
        upd(p, -1);
        rez[p] = i;
    }

    for (int i = 1; i <= n; ++i)
        fout << rez[i] << '\n';

    return 0;
}