Cod sursa(job #3371095)

Utilizator angelaAngela Visuian angela Data 28 octombrie 2026 17:33:37
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
// ok
// https://infoarena.ro/problema/schi
#include <fstream>
#define N 100100
using namespace std;

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

int ord[N]; // sirul care trebuie afisat
int v[N], n;
int A[N];    // A[x] - nr de pozitii (locuri) libere la un moment dat in intervalul [x - 2^k + 1, x]
             // k este numarul de zerouri terminale a lui x
             // 2^k este si ultimul terment din descompunerea lui x in suma de puteri ale lui 2

void Update(int pos, int v)
{
    for(int x = pos; x <= n; x += x & -x)
        A[x] += v;
}

int Query(int pos)
{
    int sum = 0;
    for(int x = pos; x ; x -= x & -x)
        sum += A[x];
    return sum;
}

// returneaza cea mai mica pozitie poz pentru care exista exact p locuri libere
// in intervalul [1...poz] exista p valori de 1
int FindKth(int p)
{
    int p2 = 1, idx = 0;
    while ((p2 << 1) <= n)
        p2 <<= 1;

    int sum = 0;
    for (; p2; p2 >>= 1)
        if (idx + p2 <= n)
        {
            if (sum + A[idx + p2] < p)
            {
                idx += p2;
                sum += A[idx];
            }
        }
    return idx + 1;
}

int main ()
{
    fin >> n;
    // initial toate locurile sunt neocupate
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        Update(i, 1); // 1 - neocupat, 0 - ocupat
    }
    int loc_real;
    for (int i = n; i >= 1; --i)
    {
        loc_real = FindKth(v[i]);
        Update(loc_real, -1);
        ord[loc_real] = i;
    }

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

	fin.close();
	fout.close();
    return 0;
}