Cod sursa(job #86989)

Utilizator marius135Dumitran Adrian Marius marius135 Data 25 septembrie 2007 23:32:58
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<stdio.h>
#define maxn 1024*1024

long val[maxn*2+4],v[maxn],n,x[maxn*2+4],t[maxn][3];

void add(long a,long b,long c,long poz,long l,long r)
{
	if( a>r || b <l) return ;
	if( a<=l && b>=r)
	{
		val[poz] = c;
		return ;
	}
	if(val[poz]!=-1) val[poz*2] = val[poz];
	add(a,b,c,poz*2,l,(l+r)/2);
	
	if(val[poz]!=-1)val[poz*2+1] = val[poz];
	add(a,b,c,poz*2+1,(l+r)/2+1,r);
	val[poz] = -1;
}
void add2(long a,long b,long c,long poz,long l,long r)
{
	if( a>r || b <l) return ;
	if(val[poz]!=-1) return ;
	if( a<=l && b>=r && x[poz] == 0)
	{
		val[poz] = c;
		return ;
	}
	x[poz] = 1;
	
	add(a,b,c,poz*2,l,(l+r)/2);
	add(a,b,c,poz*2+1,(l+r)/2+1,r);
	
}

void col(long a,long b,long c)
{
	if(a>b)
		add(b,a,c,1,1,n-1);
	else add(a,b,c,1,1,n-1);
}
void col2(long a,long b,long c)
{
	if(a>b)
		add2(b,a,c,1,1,n-1);
	else add2(a,b,c,1,1,n-1);
}

void coloreaza(long poz,long l,long r)
{
	if(val[poz]!=-1)
		{
		for(long i =l;i <= r; i++)
			v[i] = val[poz];
		return ;
		}
	if(l==r) {v[l] = 0;return ;}
	coloreaza(poz*2,l,(l+r)/2); 
	coloreaza(poz*2+1,(l+r)/2+1,r);
	
}
int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	long a,b,c,i;
	scanf("%ld %ld %ld %ld",&n,&a,&b,&c);
	for(i=1;i<=maxn*2+2;i++)
		val[i] = -1;
	for( long i = 1; i <= n-1; i++)
	{
		//col(a,b,c);
		
		/*
		printf("%ld %ld %ld\n",a,b,c);
		coloreaza(1,1,n-1);
		for(long ii=1;ii<n;ii++)
			printf("%ld\n",v[ii]);
		*/		
		t[i][0] = a;
		t[i][1] = b;
		t[i][2] = c;
		
		a = ((long long )a*(i+1))%n;
		b = ((long long )b*(i+1))%n;
		c = ((long long )c*(i+1))%n;
		
	
	}
	for( long i = n-1; i>=1;i--)
	{
		col2(t[i][0],t[i][1],t[i][2]);
	}
	coloreaza(1,1,n-1);
	for(i=1;i<n;i++)
		printf("%ld\n",v[i]);
		
	return 0;
}