Cod sursa(job #727864)

Utilizator andrey932Andrei andrey932 Data 28 martie 2012 12:27:36
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
#define MAXN 30005

int n,m,i,tura,j,k,arb[4*MAXN],poz;
void init(int nod, int st, int dr) {
	if (st<dr) {
		arb[nod]=dr-st+1;
	}
	if (st==dr) arb[nod]=st+1;
	if (st<dr) {
		int mij=(st+dr)>>1;
		if (st<=mij) init(nod*2,st,mij);
		if (mij<dr) init(nod*2+1,mij+1,dr);
	}
}

int elim(int nod, int st, int dr, int poz) {
	if (st==dr) {		
		return arb[nod];
		arb[nod]=0;
	}
	else if (st<dr) {
		arb[nod]--;
		int mij=(st+dr)>>1;

		if ((poz<=arb[nod*2])&&(arb[nod*2]>0)) {
			return elim(nod*2,st,mij,poz);
		}
		else {
			return elim(nod*2+1,mij+1,dr,poz-arb[nod*2]);
		}		
		
	}
	return -1;
}

int main() {
	fin>>n;
	init(1,0,n-1);
	k=n;
	i=0;
	tura=1;
	//for(i=0;i<=30;i++) {
	//	cout<<"arb["<<i<<"]="<<arb[i]<<"\n";
	//}
	while (k>0) {
		i+=tura;
		i%=k;
		m=elim(1,0,n-1,i);
		fout<<m<<" ";
		i--;
		k--;
		tura++;
	}	
	return 0;
}