Cod sursa(job #86355)

Utilizator ZeusCatalin Tiseanu Zeus Data 24 septembrie 2007 12:45:08
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb

#include <cstdio>

#define MN (1<<20)

int N, Amin[2*MN], A, B, C;

void update( int node, int l, int r, int n_l, int n_r, int col )
{
    int m = ( n_l + n_r ) >> 1;
    
    if( l <= n_l && n_r <= r )
    {
        Amin[node] = col;
        return;    
    } 
    
    if( l <= m ) update( 2 * node, l, r, n_l, m, col );
    if( r > m ) update( 2 * node + 1, l, r, m + 1, n_r, col );
    
    if( Amin[2*node] == Amin[2*node+1] )
        Amin[node] = col;
    else
        Amin[node] = -1;
}

int main()
{
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    
    scanf("%d %d %d %d", &N, &A, &B, &C);
    
    for( int i = 2 ; i <= N; i++ )
    {
//        printf("-> %d %d %d\n", A - 1, B - 1, C );  
         
        if( A > B ){ int aux = A; A = B; B = aux; } 
        
        update( 1, A - 1, B - 1, 0, MN - 1, C );
/*
        int v = 1;
        for( int j = 1; j < 2 * MN; j++ )
        {
             printf("%d ", Amin[j] ); 
             --v;     
             
             if( !v )
             {
                 v = j + 1;
                 printf("\n");    
             }
        }
*/
        A = ( (long long)(A) * i ) % N,
        B = ( (long long)(B) * i ) % N,
        C = ( (long long)(C) * i ) % N;  
    }
    
    for( int i = MN; i < MN + N-1; i++ )
    {
         int me = -1, aux = i;
         
         while( aux )
         {
            if( Amin[aux] != -1 )
                me = Amin[aux];
            aux >>= 1;    
         }     
         
         printf("%d\n", me );
    }
    
    printf("\n");
    
    return 0;  
}