Pagini recente » Cod sursa (job #1164792) | Cod sursa (job #1902740) | Cod sursa (job #459039) | Cod sursa (job #3255345) | Cod sursa (job #2770178)
#include <fstream>
#define MAXN 30000
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int a[4*MAXN], order[MAXN], ranks[MAXN], start;
void update(int nod){
while(nod!=1){
nod/=2;
a[nod]=a[2*nod]+a[2*nod+1];
}
}
void eraseContestant(int node){//stergem un jucator aflat pe pozitie data
while(node!=1){//cat am unde urca
a[node]--;//scad
node/=2;//si urc
}
}
int findXthGap(int x, int pass){//gasim al x-lea loc gol
//pass e parametru, o sa-l tot modific, pas=1 la primul apel
if(pass>=start){
return pass;//daca sunt jos, intorc
}
if(a[2*pass]>=x){
return findXthGap(x, 2*pass);//daca e necesar sa merg in stanga
}
else{
return findXthGap(x-a[2*pass], 2*pass+1);//daca tre' s-o iau la dreapta
}
}
int main()
{
int n; fin>>n;
start=1;
while(start<n)
start<<=1;//calculam de unde pleaca arborele de intervale
for(int i=start; i<start+n; i++){
a[i]=1;
update(i);//facem arborele
}
//citim si pozitiile
for(int i=0; i<n; i++){
fin>>order[i];
}
int pass=1;//va fi pe veci 1, ca nu dau adrese, ci valori
for(int i=n-1; i>=0; i--){
int pos=findXthGap(order[i], pass)-start+1;//gasim unde se afla al x-lea concurent
eraseContestant(findXthGap(order[i], pass));//il scoatem
ranks[pos]=i+1;//si il adaugam
}
for(int i=1; i<=n; i++){
fout<<ranks[i]<<"\n";
}
return 0;
}//si-o intrebare de final: cum sa fac sa vaf mai repede erorile de neatentie?