Cod sursa(job #723466)

Utilizator cdascaluDascalu Cristian cdascalu Data 25 martie 2012 14:53:07
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
int n,arb[400100],s,i=1;
void init(int nod,int left,int right)
{
	arb[nod]=right-left+1;
	if(left==right)
	return;
	int div=(left+right)/2;
	init(nod*2,left,div);
	init(nod*2+1,div+1,right);
	arb[nod]=arb[nod*2]+arb[nod*2+1];
}
void update(int nod,int left,int right,int x)
{
	if(left>=right)
	{
		arb[nod]=0;
		return;
	}
	int mid=(left+right)/2;
	if(x<=mid)update(nod*2,left,mid,x);
	else update(nod*2+1,mid+1,right,x);
	arb[nod]=arb[nod*2]+arb[nod*2+1];
}
int querry(int nod,int left,int right,int x)
{
	if(left>=right)
	{
		return right;
	}
	int mid=(left+right)/2;
	if(s+arb[nod*2]<x){s+=arb[nod*2];return querry(nod*2+1,mid+1,right,x);}
	else return querry(nod*2,left,mid,x);
}
int main()
{
	FILE*f=fopen("order.in","r");
	fscanf(f,"%d",&n);
	fclose(f);
	init(1,1,n);
	FILE*g=fopen("order.out","w");
	int pos=2,k;
	for(;i<=n;++i)
	{
		pos+=i%arb[1]-1;
		if(pos>arb[1])pos-=arb[1];
		if(!pos)pos=arb[1];
		s=0;
		k=querry(1,1,n,pos);
		fprintf(g,"%d ",k);
		update(1,1,n,k);
	}
	fclose(g);
	return 0;
}