Nu aveti permisiuni pentru a descarca fisierul grader_test15.ok

Cod sursa(job #90245)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 8 octombrie 2007 22:12:12
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define fin  "curcubeu.in"
#define fout "curcubeu.out"
#define Nmax 1000001

int N,a,b,c;
int col[Nmax],p[Nmax],nxt[Nmax];
int oper[Nmax][3];

int find(int x)
{
	if ( x != p[x] )
		p[x]=find(p[x]);
	return p[x];
}

void readdata()
{
	long long A,B,C;
	int i,j;

	freopen(fin,"r",stdin);
	scanf("%d",&N);
	scanf("%lld%lld%lld",&A,&B,&C);
	for (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);
		oper[i][0]=a; oper[i][1]=b; oper[i][2]=c;
	}

	for (i=N-1;i>0;--i)
	{
		a=oper[i][0]; b=oper[i][1]; c=oper[i][2];
		for (j=a;j<=b;++j)
		{
			if ( col[j] == 0 )
			{
				col[j]=c;
				if ( col[j-1] != 0 )
				{
					p[j]=find(j-1);
					nxt[p[j]]=j;
				}
				if ( p[j] == 0 )
				{	
					p[j]=j;
					nxt[j]=j;
				}
				if ( col[j+1] != 0 )
				{
					p[p[j]]=find(j+1);
				}
			}
			j=nxt[find(j)];
		}
/*		
		printf("%d %d %d\n",a,b,c);
		for (j=1;j<N;++j)
			printf("%d ",p[j]);
		printf("\n");
		for (j=1;j<N;++j)
			printf("%d ",nxt[j]);
		printf("\n\n");
		*/
	}
}

void printdata()
{
	int i;

	freopen(fout,"w",stdout);
	
	for (i=1;i<N;++i)
		printf("%d\n",col[i]);
}

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