Cod sursa(job #90350)

Utilizator ZeusCatalin Tiseanu Zeus Data 9 octombrie 2007 11:21:56
Problema Curcubeu Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb

#include <cstdio>

#define MN (1<<20)

int N, col[MN], next[MN], op[MN][3], p[MN], rank[MN], repos[MN];

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

inline void unify( int x, int y )
{
    x = find(x), y = find(y);
    if( rank[x] > rank[y] ) p[y] = x, rank[x] += rank[y];
    else p[x] = y, rank[y] += rank[x];   
}
*/

void doit( int A, int B, int C )
{
    int last = -1;
    
    for( int i = A; i <= B; i++ )
    {
         if( !col[i] )
         {
             if( last == -1 )
                 last = i;
             col[i] = C;    
             repos[i] = last;
         }
         else
         {
             if( last != -1 )
             {
                 next[ last ] = i - 1;
                 last = -1;
             }
             
             i = next[ repos[i] ];
         }
    }
    
    if( last != -1 )
         next[ last ] = B;
}

int main()
{
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    
    int A, B, C;
    scanf("%d %d %d %d", &N, &A, &B, &C);
    
    for( int i = 0; i < N - 1; i++ )
         next[i] = i;
         
    for( int i = 0; i < N - 1; i++ )
         p[i] = i,
         rank[i] = 1;
         
    for( int i = 2 ; i <= N; i++ )
    {
        if( A > B ){ int aux = A; A = B; B = aux; } 
        
        op[i-1][0] = A - 1, op[i-1][1] = B - 1, op[i-1][2] = C;
        
//        printf("%d - %d with %d\n", A-1, B-1, C );
        
        A = ( (long long)(A) * i ) % N,
        B = ( (long long)(B) * i ) % N,
        C = ( (long long)(C) * i ) % N;  
    }
    
    for( int i = N - 1; i >= 1; --i )
        doit( op[i][0], op[i][1], op[i][2] );
    
    for( int i = 0; i < N - 1; i++ )
         printf("%d\n", col[i]);
    
    return 0;  
}