Cod sursa(job #723194)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 25 martie 2012 00:51:56
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
using namespace std;

int i, p, q, N;
int A[1 << 16];

void init(int k, int st, int dr) {
	if(st == dr) {
		A[k] = 1;
		return;
	}
	
	int m = (st + dr) / 2;
	init(2 * k, st, m);
	init(2 * k + 1, m + 1, dr);
	
	A[k] = A[2 * k] + A[2 * k + 1];
}

int query(int k, int st, int dr, int nr) {
	if(st == dr)
		return st;
	
	int m = (st + dr) / 2;
	if(A[2 * k] >= nr) return query(2 * k, st, m, nr);
	else return query(2 * k + 1, m + 1, dr, nr - A[2 * k]);
}

void update(int k, int st, int dr) {
	if(st == dr) {
		A[k] = 0;
		return;
	}
	
	int m = (st + dr) / 2;
	if(q <= m) update(2 * k, st, m);
	else update(2 * k + 1, m + 1, dr);
	
	A[k] = A[2 * k] + A[2 * k + 1];
}

int main() {
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
	
	scanf("%d", &N);
	
	init(1, 1, N);
	p = 2;
	for(i = 0; i < N; i++) {
		p = (p + i - 1) % (N - i) + 1;
		q = query(1, 1, N, p);
		printf("%d ", q);
		update(1, 1, N);
	}
	
	return 0;
}