Cod sursa(job #143588)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 26 februarie 2008 18:06:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <math.h>
#include <stdio.h>

long v[1<<16], n, pzin, i;

void init(long poz, long st, long dr) {
	v[poz] = dr - st + 1;
	if (dr == st) return;
	init(poz * 2, st, (st + dr) / 2);
	init(poz * 2 + 1, (st + dr) / 2 + 1, dr);
}

long arbore(long poz, long st, long dr, long cresc) {
	if( st > cresc ) return 0;
	if( dr <= cresc) return v[poz];
	
	return arbore(poz * 2, st, (st + dr) / 2, cresc) + arbore(poz * 2 + 1, (st + dr) / 2 + 1, dr, cresc);
} 

long val(long poz, long st, long dr, long cresc) {
	if (st == dr) return st;
	if (v[poz * 2] >= cresc)   return val(poz * 2, st, (st + dr) / 2, cresc);
	else return val(poz * 2 + 1, (st + dr) / 2 + 1, dr,cresc - v[poz * 2]);
	
}
void elimina(long poz,long st,long dr,long cresc){
	if( cresc > dr || cresc < st) return;
	if( cresc >= st && cresc <= dr)
		v[poz]--;
	if( st == dr) return;
	elimina(poz * 2, st, (st + dr) / 2,cresc);
	elimina(poz * 2 + 1, (st + dr) / 2 + 1, dr, cresc);
}

int main() {
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
	freopen("order.out", "w", stdout);
	scanf("%ld", &n);
	init(1, 1, n);
	pzin = 1;
	for (i = 1; i <= n; ++i) {
		long cate = i + arbore(1, 1, n, pzin);
		cate %= (n - i + 1);
		if (cate == 0) cate = n-i+1;
		pzin = val(1,1,n,cate);
		elimina(1,1,n,pzin);
		printf("%ld ",pzin);
		
	}
	return 0;
}