Cod sursa(job #1245286)

Utilizator yololy97Olaru Bogdan-Ioan yololy97 Data 18 octombrie 2014 21:32:30
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#define N 30001
using namespace std;
int H[3 * N], n;
void build(int node, int L, int R){
	int M = (L + R) / 2;
	if(L == R)
		H[node] = 1;
	else{
		build(node * 2, L, M);
		build(node * 2 + 1, M + 1, R);
		H[node] = H[node * 2] + H[node * 2 + 1];
	}
}
void update(int node, int L, int R, int pos){
	int M = (L + R) / 2;
	if(L == R)
		H[node] = 0;
	else{
		if(pos <= M)
			update(node * 2, L, M, pos);
		else
			update(node * 2 + 1, M + 1, R, pos);
		H[node] = H[node * 2] + H[node * 2 + 1];
	}
}
int query(int node, int L, int R, int val){
	int M = (L + R) / 2;
	if(L == R)
		return L;
	if(H[node * 2] >= val)
		return query(node * 2, L, M, val);
	else
		return query(node * 2 + 1, M + 1, R, val - H[node * 2]);
}
int main(){
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
	scanf("%d ", &n);
	build(1, 1, n);
	int elimin = 2, ramas = n;
	for(int i = 1; i <= n; ++i, --ramas){
		elimin  = (elimin + i - 1) % ramas;
		if(!elimin)
			elimin = ramas;
		int poz = query(1, 1, n, elimin);
		printf("%d ", poz);
		update(1, 1, n, poz);
	}
	printf("\n");
	return 0;
}