Cod sursa(job #2491093)

Utilizator ancabdBadiu Anca ancabd Data 11 noiembrie 2019 20:02:12
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("order.in");
ofstream cout ("order.out");

using VI = vector<int>;
using VVI = vector<VI>;

int n;
VI a;

void update(int pos, int val)
{
	for(; pos <= n; pos += pos&-pos)
		a[pos] += val;
}
int query(int pos)
{
	int r = 0;
	for(; pos > 0; pos -= pos&-pos)
		r += a[pos];
	return r;
}
int binarys(int pos)
{
	int st = 1, dr = n, mijl, rez = 0;
	while (st <= dr)
	{
		mijl = (st + dr) / 2;
		if (query(mijl) >= pos)rez = mijl, dr = mijl - 1;
		else st = mijl + 1;
	}
	return rez;
}
int main()
{
	cin >> n;

	a = VI(n + 1);

    for (int i = 1; i <= n; ++ i)
        update(i, 1);

	int pos = 1, nr = n;
	for (int i = 1, actp; i <= n; ++ i)
	{
		pos += i;
		pos %= nr;
		if (pos == 0)pos = nr;
		actp = binarys(pos);
		update(actp, -1);
		nr --;
		pos --;
		cout << actp << ' ';
	}
	return 0;
}