Cod sursa(job #2755054)

Utilizator cosminradu1760Cosmin-Andrei Radu cosminradu1760 Data 26 mai 2021 19:15:25
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#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;
}