Cod sursa(job #343762)

Utilizator marinaMarina Horlescu marina Data 27 august 2009 10:45:26
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#define INPUT "curcubeu.in"
#define OUTPUT "curcubeu.out"

int tata(int i, int *next)
{
	int ii = i, aux;
	for(;next[ii]; ii = next[ii]);
	for(aux = i; next[i]; i = next[i], next[aux] = ii, aux = i) ;
	return ii;
}

int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	int n, a, b, c;
	scanf("%d %d %d %d", &n, &a, &b, &c);
	
	int *next = new int[n+1];
	int *color = new int[n+1];
	int i;
	for(i = 0; i < n; ++i) 
		color[i] = 0,
		next[i] = 0;
	
	int *queuea = new int[n-1];
	int *queueb = new int[n-1];
	int *queuec = new int[n-1];
	

	queuea[0] = a; queueb[0] = b; queuec[0] = c;
	
	for(i = 1; i < n-1; ++i)
	{
		queuea[i] = (long long)queuea[i-1]*(i+1) % n;
		queueb[i] = (long long)queueb[i-1]*(i+1) % n;
		queuec[i] = (long long)queuec[i-1]*(i+1) % n;
	}

	for(i = n-2; i >= 0; --i)
	{	
		int a = queuea[i], b = queueb[i], c = queuec[i];
		--a; --b;
		if(a > b) a+=b, b=a-b, a-=b; //interschimb
		int ii;
		for(ii = tata(a, next); ii <= b; ii = tata(ii+1, next))
			color[ii] = c,
			next[ii] = tata(b+1, next);
	}
	for(i = 0; i < n-1; ++i)
		printf("%d\n", color[i]);
	return 0;
}