Cod sursa(job #713509)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 14 martie 2012 18:35:00
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream in("order.in");
ofstream out("order.out");

int n,nc,aib[30010],p=0,pp;

inline void add(int poz,const int &val) {
	
	while(poz<=n) {
		aib[poz] += val;
		poz+=(poz&(-poz));
	}
}

inline int sum(int nr) {
	int s=0;
	
	while(nr) {
		s += aib[nr];
		
		nr -= (nr&(-nr));
	}
	return s;
}

inline int q(const int &a, const int &b) {
	int s = sum(b) - sum(a-1); 
	if(s>=0)
		return s;
	return -s;
}

inline int caut(int a, int b) {
	a = (a-1)%n + 1;
	b = (b-1)%n + 1;
	
	if(a<=b)
		return q(a,b);
	
	return q(a,n) + q(1,b);
}

int main() {
	int i,j,pas;
	
	in >> n;
	
	nc=1;
	
	for(i=1;i<=n;++i)
		add(i,1);
	
	for(i=1;i<=n;++i) {
		pas=1<<14; ++p;
		pp = (p-1)%(n-p+1) + 1;
		
		for(j=0;pas!=0;pas>>=1)
			if(j+pas<=n && caut(nc+1, nc+j+pas)<pp)
				j+=pas;
		++j;
		
		nc = (nc+j - 1)%n + 1;
		out << nc << " ";
		add(nc,-1);
	}
	
	return 0;
}