Cod sursa(job #229117)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 9 decembrie 2008 11:30:24
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN 1000100
using namespace std;
int n,x,y,z,l;
int A[MAXN],B[MAXN],C[MAXN],Next[MAXN],S[MAXN];
inline int drum(int x){
       int y=x,aux;
       for (;S[x];x=Next[x]);
       for (;S[y];){
           aux = y;
           y = Next[y];
           Next[aux] = x;
       }
       return x;
}
main(){
    int i,j;  
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);
    scanf("%d %d %d %d ",&n,&A[1],&B[1],&C[1]);
    for (i = 2; i < n; ++i){
      A[i]=(1LL*A[i-1]*i)%n;
      B[i]=(1LL*B[i-1]*i)%n;
      C[i]=(1LL*C[i-1]*i)%n;
    }
    for (i = 1; i <= n; ++i)
	Next[i] = i + 1;
    for (i=n-1;i>0;i--){
        x = min(A[i],B[i]); y = max(A[i],B[i]);
        if (S[x] == 0)
	  S[x] = C[i];
        for (j = drum(x); j <= y;j = z){
	  S[j] = C[i];
	  z = drum(j);
          Next[j] = Next[y];
        }
        Next[x] = Next[y];
    }
    for (i = 1; i < n; ++i)
	printf("%d\n",S[i]);
}