Cod sursa(job #3316999)

Utilizator amaliasasuAmalia Sasu amaliasasu Data 21 octombrie 2025 17:24:21
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
// ok
// https://infoarena.ro/problema/schi
// O(n * log^2(n))
#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] 
             // 2^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 Bs(int p) // O(log^2(n))
{
    int st = 1, dr = n, poz = n;
    while (st <= dr)
    {
        int mij = (st + dr) >> 1;
        if (Query(mij) >= p)
        {
            poz = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return poz;
}

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) // O(n * log^2 n)
    {
        loc_real = Bs(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;
}