Cod sursa(job #464895)

Utilizator S7012MYPetru Trimbitas S7012MY Data 22 iunie 2010 14:21:20
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <iostream>
using namespace std;
#define DN 1000001

int s[DN],urm[DN],a[DN],b[DN],c[DN],n;

int drum(int el) {
	int i,j;
	for(i=el; s[el]; el=urm[el]);
	while(s[i]) {
		j=i;
		i=urm[i];
		urm[j]=el;
	}
	return el;
}

int main()
{
	int i,j,x,y,z;
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	scanf("%d %d %d %d",&n,&a[1],&b[1],&c[1]);
	for(i=2; i<n; i++) {
		a[i]=(1LL*a[i-1]*i)%n;
		b[i]=(1LL*b[i-1]*i)%n;
		c[i]=(1LL*c[i-1]*i)%n;
	}
	for(i=1; i<=n; i++) urm[i]=i+1;
	for(i=n-1; i>0; i--) {
		if(a[i]<b[i]) {
			x=a[i];
			y=b[i];
		}
		else {
			x=b[i];
			y=a[i];
		}
		if(!s[x]) s[x]=c[i];
		for(j=drum(x);j<y; j=z) {
			s[j]=c[i];
			z=drum(j);
			urm[j]=urm[y];
		}
		urm[x]=urm[y];
	}
	for (i=1;i<n;i++) printf("%d\n",s[i]);
	return 0;
}