Pagini recente » Istoria paginii runda/cei_mai_mari_olimpicari_runda_2 | Cod sursa (job #3296094)
#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;
}