Pagini recente » Cod sursa (job #641964) | Cod sursa (job #2246822) | Cod sursa (job #2167761) | Cod sursa (job #297348) | Cod sursa (job #2755054)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int arbore[120001];
void build(int nod, int st, int dr)
{
int m = (st + dr) / 2;
if (st == dr) //frunza
{
arbore[nod] = 1;
return;
}
build(2 * nod, st, m); //subarbore stang
build(2 * nod + 1, m + 1, dr); //subarbore dreapt
arbore[nod] = arbore[2 * nod] + arbore[2 * nod + 1];
//nr de noduri din subarborii fii
//in care subarbore cautam copilul de eleminat
}
int searchn(int nod, int st, int dr, int poz)
{
int m = (st + dr) / 2;
if (st == dr)
return dr; //frunza
if (poz <= arbore[nod*2]) //daca pozitia copilului eliminat este mai mica sau egala cu numarul de noduri din subarborele stang cautam in stanga
return searchn(2 * nod, st, m, poz);
else //altfel cautam in dreapta
return searchn(2 * nod + 1, m + 1, dr, poz - arbore[2 * nod]);
}
void update(int nod, int st, int dr, int element)
{
if (st == dr)//dam valoarea 0 frunzei care trebuie eliminata
{
arbore[nod] = 0;
return;
}
int m = (st + dr) / 2;
if (element <= m )//daca elementul ce trebuie eliminat este mai mic ca m mergem in stanga
update(2 * nod, st, m,element);
else //altfel mergem in dreapta
update(2 * nod + 1, m + 1, dr,element);
arbore[nod] = arbore[2 * nod] + arbore[2 * nod + 1];//actualizam arborele
}
int main()
{
int i, n, poz=2, element;
fin >> n;
build(1, 1, n);
for ( i = 1; i <= n; i++)
{
poz += i-1;
while (poz > arbore[1]) //pdaca nu gasim pozitia in arbore, o decrementam pentru a fi in intervalul cerut
poz -= arbore[1];
element = searchn(1, 1, n, poz); //cautam pozitia ce trebuie eliminata
update(1, 1, n,element); // eliminam
fout<<element<<" "; //afisam ce eliminam
}
return 0;
}