Cod sursa(job #246018)

Utilizator CezarMocanCezar Mocan CezarMocan Data 19 ianuarie 2009 18:16:50
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>

using namespace std;

int n, st[70000], i, j, k, rez;

void update(int nod, int l, int r, int poz, int val) {
	int m = (l + r) / 2;
	
	if (l == r) {
		st[nod] = val;
		return;
	}
	
	if (poz <= m)
		update(nod * 2, l, m, poz, val);
	else
		update(nod * 2 + 1, m + 1, r, poz, val);
	
	st[nod] = st[nod * 2] + st[nod * 2 + 1];
	
}

void find(int nod, int l, int r, int k) {
	int m = (l + r) / 2;
	if (l == r) {
		rez = m;
		return;
	}
	if (k <= st[2 * nod])
		find(2 * nod, l, m, k);
	else
		find(2 * nod + 1, m + 1, r, k - st[2 * nod]);
}

void query(int nod, int l, int r, int poz) {
	int m = (l + r) / 2;
	if (1 <= l && r <= poz) {
		k += st[nod];
		return;
	}
	if (1 <= m)
		query(nod * 2, l, m, poz);
	if (m < poz)
		query(nod * 2 + 1, m + 1, r, poz);
}

int main() {
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
	
	scanf("%d", &n);
	for (i = 1; i <= n; i++) 
		update(1, 1, n, i, 1);
	
	rez = 1;
	for (i = 1; i <= n; i++) {
		k = 0;
		query(1, 1, n, rez);
		k = (k + i) % st[1];
		if (k == 0)
			k = st[1];
		rez = 0;
		find(1, 1, n, k);
		update(1, 1, n, rez, 0);		
		printf("%d ", rez);
	}
	
	return 0;
}