Cod sursa(job #86195)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 23 septembrie 2007 20:07:41
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#define fin  "curcubeu.in"
#define fout "curcubeu.out"
#define Nmax 2500000

int tree[Nmax],N,a,b,c;

void update(int nod,int st,int dr)
{
	int mijl;

	if ( a <= st && dr <= b)
		tree[nod]=c;
	else
	{
		mijl=(st+dr)/2;
		if (tree[nod])
			tree[2*nod]=tree[2*nod+1]=tree[nod];
		if (a <= mijl && tree[2*nod]!=c)
			update(2*nod,st,mijl);
		if (b >  mijl && tree[2*nod+1]!=c)
			update(2*nod+1,mijl+1,dr);
		if ( tree[2*nod] != tree[2*nod+1] )
			tree[nod]=0;
		else
			tree[nod]=tree[2*nod];
	}
}

void swap(int &a,int &b)
{
	int aux;
	aux=a; a=b; b=aux;
}

void readdata()
{
	long long A,B,C;

	freopen(fin,"r",stdin);
	scanf("%d",&N);
	scanf("%lld%lld%lld",&A,&B,&C);
	for (int i=1;i<N;++i)
	{
		A = ( A * i ) % N ;
		B = ( B * i ) % N ;
		C = ( C * i ) % N ;
		a = ( int ) A;
		b = ( int ) B;
		c = ( int ) C;
		if ( a > b )
			swap(a,b);
//		printf("%d %d %d\n",a,b,c);
		update(1,1,N-1);
	}
}

void query(int nod,int st,int dr)
{
	int mijl;

	if ( a == st && dr == a)
		c = tree[nod];
	else
	{
		mijl=(st+dr)/2;
		if ( a <= mijl )
		{
			if (tree[2*nod])
			{
				c=tree[2*nod];
				return ;
			}
			query(2*nod,st,mijl);
		}
		else
		{
			if (tree[2*nod+1])
			{
				c=tree[2*nod+1];
				return ;
			}
			query(2*nod+1,mijl+1,dr);
		}
	}
}

void printdata()
{
	int i;

	freopen(fout,"w",stdout);

	for (i=1;i<N;++i)
	{
		a=i; c=0;
		query(1,1,N-1);
		printf("%d\n",c);
	}
}

int main()
{
	readdata();
	printdata();
	return 0;
}