Cod sursa(job #2928484)

Utilizator matei.tudoseMatei Tudose matei.tudose Data 22 octombrie 2022 23:54:54
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;

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

int n, nr_el_baza, schiori[30005], pozitie[30005];
vector<int> graf;

void set_constant()
{
    int logar = log2(n);
    if ((1 << logar) < n)
        logar++;
    nr_el_baza = (1 << logar);
}

void build_graph(int node = 1)
{
    if (node >= nr_el_baza)
        graf[node] = 1;
    else
    {
        build_graph(2 * node);
        build_graph(2 * node + 1);
        graf[node] = graf[2 * node] + graf[2 * node + 1];
    }
}

int query(int poz, int node = 1)
{
    if (node >= nr_el_baza)
    {
        graf[node] = 0;
        return node - nr_el_baza + 1;
    }
    else
    {
        if (graf[2 * node] >= poz)
        {
            int ans = query(poz, 2 * node);
            graf[node]--;
            return ans;
        }
        else
        {
            int ans = query(poz - graf[2 * node], 2 * node + 1);
            graf[node]--;
            return ans;
        }
    }
}

int main()
{
    fin >> n;
    set_constant();
    graf.resize(2 * nr_el_baza);
    build_graph();
    for (int i = 1; i <= n; i++)
        fin >> schiori[i];
    for (int i = n; i >= 1; i--)
        pozitie[query(schiori[i])] = i;
    for (int i = 1; i <= n; i++)
        fout << pozitie[i] << "\n";
    return 0;
}