Cod sursa(job #2753814)

Utilizator andreea_07Andreea Georgescu andreea_07 Data 24 mai 2021 15:02:10
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#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)
	{
		arbore[nod] = 1;
		return; ///am ajuns jos
	}


	creare_arbore(2 * nod, st, mij);

	creare_arbore(2 * nod + 1, mij + 1, dr);

	arbore[nod] = arbore[2 * nod] + arbore[2 * nod + 1];
}

int cautare(int nod, int st, int dr, int poz)
{ int mij = (st + dr) / 2;

	if (st == dr)
		return dr;

	if (poz <= arbore[nod*2]) ///daca pozitia nodului de eliminat este mai mica decat valoarea din fiul stang cautam tot in stanga
		cautare(2 * nod, st, mij, poz);
	else
		cautare(2 * nod + 1, mij + 1, dr, poz - arbore[2 * nod]);
}

void update(int nod, int st, int dr, int element)
{
	if (st == dr)
	{
		arbore[nod] = 0;
		return;
	}

	int mij = (st + dr) / 2;
	if (element <= mij)
		update(2 * nod, st, mij,element);
	else
		update(2 * nod + 1, mij + 1, dr,element);

	arbore[nod] = arbore[2 * nod] + arbore[2 * nod + 1];
}


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])
         poz -= arbore[1];   ///modificam pozitia astfel incat sa apartina [1,n]

    element = cautare(1, 1, n, poz);

    update(1, 1, n,element);

    fout<<element<<" ";
}
fin.close();
fout.close();
	return 0;

}