Cod sursa(job #2749530)

Utilizator LordNecrateBiowCuciureanu Dragos-Adrian LordNecrateBiow Data 7 mai 2021 01:01:59
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>
#include <limits.h>

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

int Arb[120005];
int n, poz=2, x;

void construire(int nod, int left, int right)
{
	if (left == right)
	{
		Arb[nod] = 1;
		return;
	}

	int mij = (left + right) / 2;
	construire(2 * nod, left, mij);
	construire(2 * nod + 1, mij + 1, right);

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

void modificare(int nod, int left, int right)
{
	if (left == right)
	{
		Arb[nod] = 0;
		return;
	}

	int mij = (left + right) / 2;
	if (x <= mij)
		modificare(2 * nod, left, mij);
	else
		modificare(2 * nod + 1, mij + 1, right);

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

int determinare_elem(int nod, int left, int right, int poz)
{
	if (left == right)
	{
		return left;
	}

	int mij = (left + right) / 2;
	if (poz <= Arb[nod*2])
		determinare_elem(2 * nod, left, mij, poz);
	else 
		determinare_elem(2 * nod + 1, mij + 1, right, poz - Arb[2 * nod]);
}

int main()
{
	fin >> n;

	construire(1, 1, n);

	for (int i = 1; i <= n; i++)
	{
		poz += i;
		poz -= 1;
		
		while (poz > Arb[1])
			poz -= Arb[1];

		x = determinare_elem(1, 1, n, poz);
		modificare(1, 1, n);

		fout << x << " ";
	}

	return 0;
}