Cod sursa(job #539417)

Utilizator funkydvdIancu David Traian funkydvd Data 22 februarie 2011 22:18:57
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
using namespace std;
const int N = 30005;
int n, v[N * 4], ind[N], K, p;
void build(int st, int dr, int poz)
{
	int x = (st +dr) / 2;
	if(st == dr) 
	{
		ind[st] = poz; 
		return ;
	}
	build(st, x, poz * 2);
	build(x + 1, dr, poz * 2 + 1);
}
void update(int poz, int val) 
{
	int x = ind[poz];
	v[x] += val;
	for(x /= 2; x; x /= 2) v[x] = v[2 * x] + v[2 * x + 1];
}
int query(int st, int dr, int poz)
{
	if(st == dr) return st;
	int x = (st + dr) / 2;
	if(p + v[poz * 2] >= K) return	query(st, x, poz * 2);
	else 
	{
		p += v[poz * 2];
		return query(x + 1, dr, poz * 2 + 1);
	}
}
int main() 
{
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
	scanf("%d ", &n);
	build(1, n, 1);
	for(int i = 1; i <= n; ++i) update(i, 1);
	K = 1;
	int N = n, x;
	for(int i = 1; i <= N; ++i) 
	{
		K = (K + i) % n;	
		if(K == 0) K = n;
		p = 0;
		x = query(1, N, 1);
		printf("%d ", x);
		update(x, -1);
		--n, --K;
		if(K == 0) K = n;
	}
	printf("\n");
	return 0;
}