Cod sursa(job #2754085)

Utilizator Virgil993Virgil Turcu Virgil993 Data 25 mai 2021 00:53:39
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#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;
}