Cod sursa(job #2491103)

Utilizator ancabdBadiu Anca ancabd Data 11 noiembrie 2019 20:14:40
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 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 build(int node, int st, int dr)
{
	if (st == dr)
    {
        a[node] = 1;
        return;
    }

    int mijl = (st + dr)/2;

    build(2 * node, st, mijl);
    build(2 * node + 1, mijl + 1, dr);

    a[node] = a[2 * node] + a[2 * node + 1];
}

void update(int node, int st, int dr, int pos)
{
    if (st == dr)
    {
        a[node] = 0;
        return;
    }

    int mijl = (st + dr)/2;

    if (pos <= mijl)update(2 * node, st, mijl, pos);
    else update(2 * node + 1, mijl + 1, dr, pos);

    a[node] = a[2 * node] + a[2 * node + 1];
}
int query(int node, int st, int dr, int pos)
{
	if (st == dr)return st;

	int mijl = (st + dr)/2;

	if (a[2 * node] >= pos)return query(2 * node, st, mijl, pos);
	else return query(2 * node + 1, mijl + 1, dr, pos - a[2 * node]);
}

int main()
{
	cin >> n;

	a = VI(4 * n + 1);

    build(1, 1, n);

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