Cod sursa(job #3184117)

Utilizator rapidu36Victor Manz rapidu36 Data 14 decembrie 2023 15:01:01
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>

using namespace std;

const int N = 3e4;
const int L = 14;

int n, aib[N+1], locul_init[N+1], concurent[N+1];

void init_aib()
{
    for (int i = 1; i <= n; i++)
    {
        int p2 = (i & (-i));
        ///intervalul pentru care retinem date in aib[i] este [i-p2+1, i]
        aib[i] = p2;
        ///initial numarul de locuri libere este tot intervalul retinut pe poz. i
    }
}

int cautare(int poz_ini)
{
    ///caut folsind aib cea mai mica pozitie p cu propr. ca numarul de locuri libere
    ///pana la p este < poz_ini (adica suma din aib)
    int p = 0, pas = 1 << L;
    while (pas != 0)
    {
        if (p + pas <= n && aib[p+pas] < poz_ini)
        {
            poz_ini -= aib[p+pas];
            p += pas;
        }
        pas /= 2;
    }
    return p + 1;
}

void actualizare(int poz, int val)
{
    while (poz <= n)
    {
        aib[poz] += val;
        int p2 = (poz & (-poz));
        poz += p2;
    }
}

int main()
{
    ifstream in("schi.in");
    ofstream out("schi.out");
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> locul_init[i];
    }
    init_aib();
    for (int i = n; i >= 1; i--)
    {
        int poz_finala = cautare(locul_init[i]);
        actualizare(poz_finala, -1);
        concurent[poz_finala] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        out << concurent[i] << "\n";
    }
    in.close();
    out.close();
    return 0;
}