Cod sursa(job #3296094)

Utilizator Lex._.Lexi Guiman Lex._. Data 11 mai 2025 12:49:23
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <bits/stdc++.h>
#define NMAX 30000
using namespace std;

int clasament_initial[NMAX]; ///clasamentul citit
int clasament_final[NMAX]; ///clasamentul final

int poz_libera(int loc, vector<int> &aib) ///cauta prima pozitie pentru care exista loc pozitii libere in clasamentul final inaintea ei
{
    int n=aib.size()-1;
    int putere_2=1; ///cea mai mare putere a lui 2 mai mica decat n
    while((putere_2<<1)<=n)
        putere_2<<=1;

    int poz=0; ///ultima pozitie pentru care nu exista loc pozitii libere in clasamentul final ei
    while(putere_2!=0) ///cat timp puterea lui 2 este mai mare ca 0
    {
        int sum_poz=putere_2+poz;
        int lungime=(sum_poz&(-sum_poz)); ///lungimea intervalului pe care verificam

        if(sum_poz<=n && lungime-aib[sum_poz]<loc) ///daca intre poz si sum_poz sunt mai putin de loc valori de 1 (adica cel putin loc locuri libere)
        {
            loc-=lungime-aib[sum_poz];
            poz=sum_poz;
        }
        putere_2>>=1; ///micsoram puterea lui 2
    }
    return poz+1; ///returnam prima pozitie pentru care exista loc pozitii libere in clasamentul final inaintea ei
}

void actualizare(int poz, vector<int> &aib) ///actualizeaza aib-ul la pozitia poz
{
    int n=aib.size()-1;
    while(poz<=n)
    {
        aib[poz]++;
        poz+=(poz&(-poz));
    }
}

int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> clasament_initial[i]; ///citim clasamentul initial
    }
    vector<int> aib(n+1); ///arborele indexat binar
    for(int i=n; i>=1; i--) ///luam fiecare concurent si il punem pe a clasament_initial[i]-a pozitie libera
    {
        int pozitie=poz_libera(clasament_initial[i], aib); ///calculam pozitia in clasamentul final a lui i
        clasament_final[pozitie]=i; ///il punem pe concurentul i in clasamentul final
        actualizare(pozitie, aib); ///actualizam aib-ul
    }
    for(int i=1; i<=n; i++)
        cout << clasament_final[i] << "\n"; ///afisam clasamentul final

    return 0;
}