Cod sursa(job #2645194)

Utilizator LAURENTIU-MARIAN.VASILESCUVasilescu Laurentiu-Marian LAURENTIU-MARIAN.VASILESCU Data 27 august 2020 14:43:45
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
using namespace std;

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

int game[31000],n;

void gameStepUp(int position, int x)
{
	for (int i = position; i <= n; i += (i & -i))
		game[i] += x;
}
int findPosition(int position)
{
	int i = 0;
	for (int p = 1 << 15; p; p >>= 1)
		if (i + p <= n && game[i + p] < position)
		{
			position -= game[i + p];
			i += p;
		}
	return i + 1;
}

int main()
{
	fin >> n;
	for (int i = 1; i <= n; ++i)
		gameStepUp(i, 1);

	int k = 1, nr = n;
	for (int i = 1; i <= n; ++i)
	{
		k += i;
		k %= nr;
		if(k == 0)
            k = nr;

        int aux = findPosition(k);
        gameStepUp(aux, -1);
		nr -= 1;
		k -= 1;

		fout << aux << " ";
	}
	return 0;
}