Cod sursa(job #299148)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 6 aprilie 2009 16:40:33
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
using namespace std;

#include <queue>
#include <bitset>

#define f first
#define s second
#define II inline
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN  "curcubeu.in"
#define OUT "curcubeu.out"
#define N_MAX 1<<20

typedef vector<int> VI;
typedef pair<int,int> pi;

int N,T[N_MAX],C[N_MAX];
vector< pair<pi,int> > V;

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d",&N);
	
	V.resize(N);
	scanf("%d%d%d",&V[1].f.f,&V[1].f.s,&V[1].s);
	
	FOR(i,2,N-1)
	{
		V[i].f.f = (V[i-1].f.f * i) % N;
		V[i].f.s = (V[i-1].f.s * i) % N;
		V[i].s = (V[i-1].s * i ) % N;
	}
	
	FOR(i,1,N-1)
		if(V[i].f.f > V[i].f.s)
			swap(V[i].f.f,V[i].f.s);
	--N;
}

II int rep(int x)
{
	return T[x] = (T[x]!=x?rep(T[x]):x);
}

II void add(int x,int y)
{
	T[x] = y;
}

II void solve()
{
	int r1,r2;
	
	T[0] = 1;
	FOR(i,1,N)
		T[i] = i;
	T[N+1] = N;	
	FOR(i,1,N/2)
		swap(V[i],V[N-i+1]);
	
//	FOR(i,1,N)
//		printf("%d %d : %d\n",V[i].f.f,V[i].f.s,V[i].s);
	FOR(i,1,N)
		for(int j= (rep(V[i].f.f)==V[i].f.f?V[i].f.f:rep(V[i].f.f) + 1);j <= V[i].f.s;j = T[j]+1)
		{
			C[j] = V[i].s;
			if(C[j-1] && (r1=rep(j-1)) ^ (r2=rep(j)) )
				add(r1,r2);
			if(C[j+1] && (r1=rep(j-1)) ^ (r2=rep(j+1)) )
				add(r1,r2);
		}	
	FOR(i,1,N)
		printf("%d\n",C[i]);	
//	printf("Time : %d ms\n",clock() );
}

int main()
{
	scan();
	solve();
	return 0;
}