Pagini recente » Cod sursa (job #70163) | Cod sursa (job #85111) | Cod sursa (job #216822) | Monitorul de evaluare | Cod sursa (job #801427)
Cod sursa(job #801427)
#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;
}