Cod sursa(job #234724)

Utilizator ProtomanAndrei Purice Protoman Data 21 decembrie 2008 20:38:04
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#include <algorithm>
#define mx 150010

using namespace std;

int n, gs;
int ai[mx];

void update_ai(int nod, int p, int u, int key, int ct)
{
	if (p == u)
	{
		ai[nod] = ct;
		return;
	}
	int m = (p + u) / 2;
	if (key <= m)
		update_ai(2 * nod, p, m, key, ct);
	else update_ai(2 * nod + 1, m + 1, u, key, ct);
	ai[nod] = ai[nod * 2] + ai[nod * 2 + 1];
}

int query_ai(int nod, int p, int u, int key)
{
	if (p == u)
		return p;
	int m = (p + u) / 2;
	if (ai[nod * 2] >= key)
		query_ai(nod * 2, p, m, key);
	else query_ai(nod * 2 + 1, m + 1, u, key - ai[nod * 2]);
}		

int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	scanf("%ld", &n);
	for (int i = 1; i <= n; update_ai(1, 1, n, i, 1), i++);
	for (int i = 1, et = 1; i <= n; printf("%ld ", gs), i++)
	{
		et = (et + i - 1) % ai[1] + 1;
		gs = query_ai(1, 1, n, et);
		update_ai(1, 1, n, gs, 0);
		et--;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}