Cod sursa(job #856787)

Utilizator deea101Andreea deea101 Data 16 ianuarie 2013 22:34:20
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int arb[120100],n,x=1;
void update(int i, int nod, int val, int st, int dr)
{
	if(st==dr) arb[i]=val;
	else
	{
		int mij;
		mij=(st+dr)/2;
		if(nod<=mij) update(2*i,nod,val,st,mij);
		else update(2*i+1,nod,val,mij+1,dr);
		
		arb[i]=arb[2*i]+arb[2*i+1];
	}
}
int query(int i, int nr, int st, int dr)
{
	if(st==dr) return st;
	else
	{
		int mij;
		mij=(st+dr)/2;
		if(nr<=arb[2*i]) return query(2*i,nr,st,mij);
		else return query(2*i+1,nr-arb[2*i],mij+1,dr);
	}
}
int main()
{
	f>>n;
	int i,poz;
	for(i=1;i<=n;i++)
		update(1,i,1,1,n);
	for(i=1;i<=n;i++)
	{
		x=(x+i)%arb[1];
		if(x==0) x=arb[1];
		poz=query(1,x,1,n);
		g<<poz<<' ';
		update(1,poz,0,1,n);
		x--;
	}
}