Cod sursa(job #2876055)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 22 martie 2022 21:43:24
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

#define z(x) ((x)&(-x))

using namespace std;

const int N = 3 * 1e4 + 1;
int a[N], n;
int v[N];

struct binary_tree
{

    int values[N];

    binary_tree()
    {
        fill(values + 1, values + N + 1, 0);
    }

    void update(int nod, int val)
    {
        for ( int i = nod; i <= n; i += z(i))
        {
            values[i] += val;
        }
    }

    int query(int nod)
    {
        int sum = 0;
        for( int i = nod; i >= 1; i -= z(i) )
        {
            sum += values[i];
        }
        return sum;
    }

    int caut_bin(int val)
    {
        int poz = 1;
        for( int i = n; i >= 1; i >>= 1)
        {
            while(poz + i <= n and query(poz + i - 1) < val)
                poz += i;
        }
        return poz;
    }
};
binary_tree TREE;



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


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

    for(int i = n; i >= 1; i--)
    {
        int ans = TREE.caut_bin(v[i]);
        a[ans] = i;
        TREE.update(ans, -1);
    }

    for( int i = 1; i <= n; i++)
    {
        cout << a[i] << '\n';
    }
    return 0;
}