Cod sursa(job #801427)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 24 octombrie 2012 12:12:12
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<stdio.h>

#define maxn 1000000

FILE*f=fopen("curcubeu.in","r");
FILE*g=fopen("curcubeu.out","w");

int n,A,B,C;
int T[maxn],Rg[maxn],left[maxn],right[maxn],sol[maxn];
int a[maxn],b[maxn],c[maxn];

inline int min ( const int &a , const int &b ){
	return a <= b ? a : b;
}

inline int max ( const int &a , const int &b ){
	return a >= b ? a : b;
}

inline void unify ( const int &x , const int &y ){
	
	if ( Rg[x] > Rg[y] ){
		T[y] = x;
		left[x] = min(left[x],left[y]);
		right[x] = max(right[x],right[y]);
	}
	else{
		T[x] = y;
		left[y] = min(left[y],left[x]);
		right[y] = max(right[y],right[x]);
	}
	
	if ( Rg[x] == Rg[y] ){
		++Rg[y];
	}
}

inline int root ( int nod ){
	int R;
	for ( R = nod ; T[R] != R ; R = T[R] );
	
	while ( nod != T[nod] ){
		int aux = T[nod];
		T[nod] = R;
		nod = aux;
	}
	
	return R;
}

int main () {
	
	fscanf(f,"%d %d %d %d",&n,&A,&B,&C);
	for ( int i = 1 ; i < n ; ++i ){
		a[i] = A; b[i] = B; c[i] = C;
		A = (1LL*A*(i+1))%n;
		B = (1LL*B*(i+1))%n;
		C = (1LL*C*(i+1))%n;
		
		T[i] = i; Rg[i] = 1; left[i] = right[i] = -1;
	}
	
	for ( int i = n-1 ; i >= 1 ; --i ){
		int st = a[i] <= b[i] ? a[i] : b[i];
		int dr = a[i] > b[i] ? a[i] : b[i];
		
		for ( int poz = st ; poz <= dr ; ){
			int next = right[root(poz)];
			
			if ( next == -1 ){
				left[poz] = right[poz] = poz;
				sol[poz] = c[i];
				if ( poz > 1 && right[root(poz-1)] != -1 ){
					unify(root(poz-1),poz);
				}
				if ( poz <= n-2 && right[root(poz+1)] != -1 ){
					unify(root(poz+1),root(poz));
				}
				poz = right[root(poz)]+1;
			}
			else{
				poz = next+1;
			}
		}
	}
	
	for ( int i = 1 ; i < n ; ++i ){
		fprintf(g,"%d\n",sol[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}