Cod sursa(job #3149740)

Utilizator dragutamihai1234Draguta Mihai dragutamihai1234 Data 11 septembrie 2023 20:16:22
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

int n;
vector <int> place, sol;

class Fenwick
{
private:
    vector <int> a;
    int _n;

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

public:

    Fenwick(int n)
    {
        a.resize(n + 1);
        _n = n;
    }

    void update(int pos, int val)
    {
        for (int i = pos; i <= _n; i += lsb(i))
            a[i] += val;
    }

    long long query(int pos)
    {
        long long ans = 0;
        for (int i = pos; i > 0; i -= lsb(i))
            ans += a[i];

        return ans;
    }

    int binarySearch(int x)
    {
        int r, pas, sum;
        r = 0;
        pas = 1 << 17;
        sum = 0;
        while(pas)
        {
            if(r + pas <= n  &&  sum + a[r + pas] < x)
            {
                sum += a[r + pas];
                r += pas;
            }

            pas >>= 1;
        }
        return r + 1;
    }
};

int main()
{
    ios_base ::sync_with_stdio(0);
    cin.tie(0);

    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    cin >> n;
    place.resize(n + 1);
    sol.resize(n + 1);
    Fenwick aib(n);

    for(int i = 1; i <= n; i ++)
    {
        cin >> place[i];
        aib.update(i, 1);
    }

    for(int i = n; i >= 1; i --)
    {
        int poz = place[i];
        poz = aib.binarySearch(poz);
        aib.update(poz, -1);
        sol[poz] = i;
    }

    for(int i = 1; i <= n; i++)
        cout << sol[i] << "\n";
    return 0;
}