Cod sursa(job #87376)

Utilizator CommanderKUPB - Andrei Homescu CommanderK Data 27 septembrie 2007 02:07:41
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 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;

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

struct Node
{
    int clr, rank, pp, nw;
} vs[MAXN];

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

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

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

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

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++ )
        vs[i].pp = i, vs[i].nw = 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( vs[fi].clr == 0 )
            j = fi;
        else
            j = vs[findParent( fi )].nw;
        for( ; j <= li ; )
        {
            vs[j].clr = ints[i].c;
            if( vs[j - 1].clr )
                join( j - 1, j );
            j++;

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

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