Cod sursa(job #828216)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 3 decembrie 2012 13:46:49
Problema Order Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>

#define fs (node << 1)
#define fd ((node << 1) + 1)
#define mid ((lf + rt) >> 1)

int aint[1 << 17];

inline void build_tree(int node, int lf, int rt) {
	if(lf == rt) {
		aint[node] = 1;
		return ;
	}
	build_tree(fs, lf, mid);
	build_tree(fd, mid + 1, rt);

	aint[node] = aint[fs] + aint[fd];
}
inline void update(int node, int lf, int rt, int poz) {
	if(lf == rt) {
		aint[node] = 0;
		return ;
	}
	if(poz <= mid) update(fs, lf , mid , poz);
	if(poz > mid) update(fd, mid + 1, rt, poz);
	aint[node] = aint[fs] + aint[fd];
}
inline int query(int node, int lf, int rt, int val) {
	if(lf == rt)
		return lf;
	if(val > aint[fs]) return query(fd, mid + 1, rt, val - aint[fs]);
	return query(fs, lf, mid, val);
}
int main(int argc, char **argv) {
	FILE *f = fopen("order.in", "r");
	FILE *g = fopen("order.out", "w");
	
	int n, current;

	fscanf(f, "%d", &n);

	build_tree(1, 1, n);
	
	current = 1;
	int i;	
	for(i = 1; i <= n; ++i) {
		current = (current + i) % aint[1];
		if(current == 0)
			current = aint[1];
		
		int sol = query(1, 1, n, current);
		fprintf(g, "%d ", sol);
		
		update(1, 1, n, sol);
		
		current--;
	}
	return 0;

}