Cod sursa(job #87238)

Utilizator CommanderKUPB - Andrei Homescu CommanderK Data 26 septembrie 2007 21:13:54
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 kb
// 50/100
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;

#define	REP( i, n )         for( (i) = 0 ; (i) < (n) ; (i)++ )
#define	IREP( i, n )	    for( (i) = (n) - 1 ; (i) >= 0 ; (i)-- )
#define REPV( i, a, b )     for( (i) = (a) ; (i) <= (b) ; (i)++ )
#define IREPV( i, a, b )    for( (i) = (b) ; (i) >= (a) ; (i)-- )
#define REPIT( it, x )      for( (it) = (x).begin( ) ; (it) != (x).end( ) ; (it)++ )
#define ALL( x )            (x).begin( ), (x).end( )
#define MP                  make_pair
#define PB                  push_back
#define CLR( x )            memset( (x), 0, sizeof( x ) )
#define CLRV( x, v )        memset( (x), (v), sizeof( x ) )
#define CPY( y, x )         memcpy( (y), (x), sizeof( x ) )
#define	X                   first
#define Y                   second

typedef long long Ll;
typedef pair< int, int > Pii;
typedef pair< Ll, Ll > Pll;
typedef vector< int > Vi;
typedef vector< Ll > Vl;
typedef vector< string > Vs;

const int INF = 0x3f3f3f3f;
const Ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
const int MAXN = 1048576;
int n;
int clr[MAXN], rank[MAXN], pp[MAXN], nw[MAXN];

struct Interval
{
    int a, b, c;
} ints[MAXN];

inline int findParent( int vf )
{
    if( vf == pp[vf] )
        return vf;

    register int pvf;
    for( pvf = vf ; pp[pvf] != pvf ; pvf = pp[pvf] );
    for( ; vf != pvf ; )
    {
        int op = pp[pvf];
        pp[pvf] = pvf;
        vf = op;
    }
    return pvf;
}

inline void join( int v1, int v2 )
{
    int pv1 = findParent( v1 ),
        pv2 = findParent( v2 ),
        maxnw = max( nw[pv1], nw[pv2] );

    if( pv1 == pv2 )
        return;
    if( rank[pv1] < rank[pv2] )
    {
        pp[pv1] = pv2;
        nw[pv2] = maxnw;
    }
    else
    {
        pp[pv2] = pv1;
        nw[pv1] = maxnw;
        if( rank[pv1] == rank[pv2] )
            rank[pv1]++;
    }
}

int main( )
{
    freopen( "curcubeu.in", "r", stdin );
    freopen( "curcubeu.out", "w", stdout );

    int i, j;
    scanf( "%d%d%d%d", &n, &ints[1].a, &ints[1].b, &ints[1].c );
    for( i = 2 ; i < n ; i++ )
    {
        ints[i].a = ((Ll)ints[i - 1].a * (Ll)i) % n;
        ints[i].b = ((Ll)ints[i - 1].b * (Ll)i) % n;
        ints[i].c = ((Ll)ints[i - 1].c * (Ll)i) % n;
    }

    for( i = 0 ; i < n ; i++ )
        clr[i] = rank[i] = 0, pp[i] = i, nw[i] = i + 1;
    for( i = n - 1 ; i > 0 ; i-- )
    {
        int fi = min( ints[i].a, ints[i].b ),
            li = max( ints[i].a, ints[i].b );

        if( clr[fi] == 0 )
            j = fi;
        else
            j = nw[findParent( fi )];
        for( ; j <= li ; )
        {
            clr[j] = ints[i].c;
            if( clr[j - 1] )
                join( j - 1, j );
            j++;

            if( clr[j] )
            {
                if( clr[j - 1] )
                    join( j - 1, j );
                j = nw[findParent( j )];
            }
        }
    }

    for( i = 1 ; i < n ; i++ )
        printf( "%d\n", clr[i] );
    return 0;    
}