Pagini recente » Monitorul de evaluare | Cod sursa (job #86581) | Cod sursa (job #1962174) | Cod sursa (job #1333678) | Cod sursa (job #2754085)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int arbore[120001];
void creare_arbore(int nod, int st, int dr)
{ int mij = (st + dr) / 2;
if (st == dr) // am ajuns la frunza
{
arbore[nod] = 1;
return;
}
//in arbore[nod] memoram cate noduri sunt in cei doi subarbori fii si de asemenea in ce subarbore sa cautam copilul ce trebuie eliminat
creare_arbore(2 * nod, st, mij); //subarbore stanga
creare_arbore(2 * nod + 1, mij + 1, dr);//subarbore dreapta
arbore[nod] = arbore[2 * nod] + arbore[2 * nod + 1];
}
int cautare(int nod, int st, int dr, int poz)
{ int mij = (st + dr) / 2; //copii fiind indexati de la 1 la n putem returna doar indexul nodului pe care vrem sa il eliminam
if (st == dr)
return dr; //am ajuns la 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 cautare(2 * nod, st, mij, poz);
else //altfel cautam in dreapta
return cautare(2 * nod + 1, mij + 1, dr, poz - arbore[2 * nod]);
}
void update(int nod, int st, int dr, int element)
{
if (st == dr)//am ajuns la frunza ce trebuie eliminata deci ii dam valoarea 0
{
arbore[nod] = 0;
return;
}
int mij = (st + dr) / 2;
if (element <= mij)//daca elementul ce trebuie eliminat este mai mic ca mij mergem in stanga altfel mergem in dreapta
update(2 * nod, st, mij,element);
else
update(2 * nod + 1, mij + 1, dr,element);
arbore[nod] = arbore[2 * nod] + arbore[2 * nod + 1];//actualizam vectorul arbore cu noiile valori
}
int main()
{int i, n, poz=2, element;
ifstream fin("order.in");
ofstream fout("order.out");
fin >> n;
creare_arbore(1, 1, n);
for ( i = 1; i <= n; i++)
{ poz += i;
poz -= 1;
while (poz > arbore[1])//ne asiguram ca pozitia este in arbore si daca nu, o decrementam pentru a fi in intervalul cerut
poz -= arbore[1];
element = cautare(1, 1, n, poz); //cautam in arbore pozitia ce trebuie eliminata
update(1, 1, n,element); // eliminam pozitia
fout<<element<<" "; //afisam elementul scos
}
return 0;
}