Pagini recente » Cod sursa (job #1177786) | Cod sursa (job #774984) | Cod sursa (job #2623145) | Cod sursa (job #738934) | Cod sursa (job #87376)
Cod sursa(job #87376)
// 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;
}