Cod sursa(job #2488283)

Utilizator ancabdBadiu Anca ancabd Data 6 noiembrie 2019 17:37:35
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
using namespace std;

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

int aib[220022], n, x = 1;
bool vis[110011];

inline void Update(int poz)
{
	for (int i = poz; i <= 2 * n; i += i & -i)
		++aib[i];
}

inline int Query(int poz)
{
	int s = 0;
	for (int i = poz; i > 0; i -= i & -i)
		s += aib[i];
	return s;
}
	
int main()
{
	fin >> n;
	for (int p = 1; p <= n; ++p)
	{
		x = x + p + Query(x + p) - Query(x);
		while (x > n)
			x -= n;
		while (vis[x])
		{
			++x;
			if (x > n)
				x -= n;
		}
		fout << x << ' ';
		vis[x] = true;
		Update(x);
		Update(n + x);
	}
}