Pagini recente » Cod sursa (job #3198309) | Cod sursa (job #3164532) | Cod sursa (job #1173061) | Cod sursa (job #640635) | Cod sursa (job #852518)
Cod sursa(job #852518)
#include <fstream>
using namespace std;
int arbInt[1<<17 + 1];
// fiecare nod e 0/1 a fost sau nu eliminat copilul i
// eu tin suma pe intervale
int val, poz, raspuns;
void actualizeaza(int nod, int li, int ls){
// actualizeaza nodul poz, cu informatia val
if(li == ls){
arbInt[nod] = val;
return;
}
int mij = (li + ls) / 2;
if(poz <= mij){
actualizeaza(nod * 2, li, mij); // o iau in stanga
}else{
actualizeaza(nod * 2 +1, mij + 1, ls);
}
arbInt[nod] = arbInt[nod * 2] + arbInt[nod * 2 +1]; // e suma celor doi fii ai sai
}
void cauta(int nod, int li, int ls){
//cauta valoarea; pun raspunsul in raspuns
if(li == ls){
raspuns = li;
return;
}
int mij = (li + ls) / 2;
if(val <= arbInt[2 * nod]){ // daca imi ajunge ce e in stanga
cauta(2 * nod, li, mij);
}else{
val -= arbInt[2 * nod];
cauta(2 * nod + 1, mij +1, ls);
}
}
int main(){
ifstream fin("order.in");
ofstream fout("order.out");
int n;
fin>>n;
int i;
for(i = 1; i <= n; i++){
val = 1;
poz = i;
actualizeaza(1,1,n); // nod, li, ls
}
int catiDeUnuInStanga = 2;
for(i = 1; i <= n; i++){
catiDeUnuInStanga = (catiDeUnuInStanga - 1 + i - 1) % (n - i + 1) + 1;
// am cu 1 mai putin fata de ultima data, pentru ca pe unul tocmai l-am scos data trecuta
// mai scad un 1, pentru ca adun un la final; adun un unu la final, pentru ca modulul imi da de la 0
// mai adun un 1 la a doua paranteza, pentru ca pana acum am eliminat doar i - 1 copii, deci mai am n - (i - 1) de 1
val = catiDeUnuInStanga;
cauta(1,1,n);
fout<<raspuns<<" ";
val = 0;
poz = raspuns;
actualizeaza(1,1,n);
}
return 0;
}