Cod sursa(job #2290210)

Utilizator max945Maxim C max945 Data 25 noiembrie 2018 23:31:57
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 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;
	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)) {	
	
		int rez=arb[nod];
	
		arb[nod]=0;
	
		return rez;		
	}
	else if (st<dr) {
		arb[nod]--;
		int mij=(st+dr)>>1;
		int ls,ld;
		if ( (st==mij) && (arb[nod*2]>0) ) ls=1; else ls=arb[nod*2];
		if (dr==mij+1) ld=1; else ld=arb[nod*2+1];
	
		if (poz<=ls) return elim(nod*2,st,mij,poz);
	
		else if (mij+1<=dr)       return elim(nod*2+1,mij+1,dr,poz-ls);
	
		
	
		
	
	}
	
	return -1;
	
}
int main() {
	fin>>n;
	init(1,1,n);
	k=n;
	i=0;
	tura=1;
	i=1;
	while (k>0) {
		i+=tura;
		i%=k;
		if (i==0) i=k;
		m=elim(1,1,n,i);

		fout<<m<<" ";
		i--;
		k--;
		tura++;
	}	
	fout<<"\n";
	fout.close();
	return 0;
}