Cod sursa(job #519856)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 ianuarie 2011 18:29:43
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
using namespace std;
#define N 30010

int n,n1;
int a[N];
int unde=1;

inline int nrb(int x) {
	return ((x&(x-1))^x);
}

inline void inc(int i) {
	for(; i<=n; i+=nrb(i))
		++a[i];
}

inline void dec(int i) {
	for(; i<=n; i+=nrb(i))
		--a[i];
}

inline int sum(int i) {
	int ret = 0;
	for(; i>0; i-=nrb(i))
		ret += a[i];
	return ret;
}

inline int getNext(int pas) {
	pas += sum(unde);
	pas %= n1;
	if(pas==0)
		pas = n1;

	int p=1,u=n;
	int m;
	while(p<u) {
		m = (p+u)>>1;
		if(sum(m)>=pas)
			u = m;
		else
			p = m+1;
	}

	dec(p);
	--n1;
	unde = p;
	return p;
}

int main() {
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);

	scanf("%d",&n);
	n1 = n;

	for(int i=1; i<=n; ++i)
		inc(i);
	for(int i=1; i<n; ++i)
		printf("%d ",getNext(i));
	printf("%d\n",getNext(n));

	return 0;
}