Cod sursa(job #533572)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 14 februarie 2011 11:13:14
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#define Nmax 1000010

int T[Nmax], a[Nmax], sol[Nmax] ; 
int i, n, A, B, C, t, j, ls, ld, aux ;

struct interval { int x,y,c; } q[Nmax] ;

int find ( int x ) 
{
	int R = x , y ;
	
	for( ; R != T[R] ; R = T[R] ) ;
	
	for( ; x != T[x] ;  )
	{
		y = T[x] ;
		T[x] = R ;
		x = y ;
	}
	
	return R ;
}

int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	
	scanf("%d %d %d %d",&n,&A,&B,&C);
	
	q[1].x = A ; q[1].y = B ; q[1].c = C ;

	for( i = 2 ; i < n ; i++ )
	{
		q[i].x = ( q[i-1].x * i ) % n ;
		q[i].y = ( q[i-1].y * i ) % n ;
		q[i].c = ( q[i-1].c * i ) % n ;
	}
	
	for( i = 1 ; i <= n ; i++ )
	{
		T[i] = i ;
		a[i] = i ;
	}
	
	for( i = n - 1 ; i ; i-- )
	{
		ls = q[i].x ; 
		ld = q[i].y ;
		
		if( ls > ld ) { aux = ls ; ls = ld ; ld = aux ; } 
		
		t = find( ls ) ; 
		
		for( j = a[t] ; j <= ld ; )
			if( a[j] == j  )
			{
				sol[j] = q[i].c ; 
				T[j] = t ;  
				j++;
			}
			else
			{
				T[j] = t ;
				j = a[j] ;
			}			
		a[t] = j ;	
		
		if( a[j] != j  )
		{
			T[j] = t ;
			a[t] = a[j] ;
		}
	}
	
	for( i = 1 ; i < n ; i++ )
		printf("%d\n",sol[i]);
	
	return 0;
}