Cod sursa(job #2589639)

Utilizator georgecristian2002Raducanu George-Cristian georgecristian2002 Data 26 martie 2020 17:36:00
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
using namespace std;

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

int aib[30001],n;

void actualizare(int poz, int val)
{
	for (int i = poz; i <= n; i += (i & -i))
		aib[i] += val;
}
  int interogare(int poz)
{
	int i = 0;
	for (int p = 1 << 15; p; p >>= 1)
		if (i + p <= n && aib[i + p] < poz)
		{
			poz -= aib[i + p];
			i += p;
		}
	return i + 1;
}

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

	int pos = 1, nr = n;
	for (int i = 1; i <= n; ++i)
	{
		pos += i;
		pos %= nr;
		pos = (pos == 0) ? nr : pos;

		int act = interogare(pos);

		actualizare(act, -1);
		--nr;
		--pos;

		fout << act << " ";
	}
	return 0;
}