Cod sursa(job #85961)

Utilizator megabyteBarsan Paul megabyte Data 23 septembrie 2007 12:25:40
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Autumn Warmup 2007, Runda 2 Marime 1.74 kb
#include <cstdio>
#define INF "curcubeu.in"
#define OUF "curcubeu.out"
#define DMAX 2097152
using namespace std;

struct nod
{
	int p,c;//prioritate si culoare
}segt[DMAX]={0},x;
int a,b;

void insert(int nd,int st,int dr)
{
	if(a<=st&&dr<=b) segt[nd]=x;
	else
	{
		int mij;
		mij=(st+dr)/2;
		if(a<=mij) insert(2*nd,st,mij);
		if(b>mij) insert(2*nd+1,mij+1,dr);
	}
}

void update(int nd,int st,int dr)
{
	if(st==dr) 
	{
		if(segt[nd/2].p>segt[nd].p) segt[nd]=segt[nd/2];
	}
	else
	{
		int mij;
		mij=(st+dr)/2;
		if(segt[nd/2].p>segt[nd].p) segt[nd]=segt[nd/2];
		if(st<=mij) update(2*nd,st,mij);
		if(dr>mij) update(2*nd+1,mij+1,dr);
	}
}

int query(int nd,int st,int dr,nod dad)
{
	if(a<=st&&dr<=b)
	{
//		if(dad.p>segt[nd].p) segt[nd]=dad;
		return segt[nd].c;	
	}
	else
	{
//		if(dad.p>segt[nd].p) segt[nd]=dad;
		int l,r,mij;
		mij=(st+dr)/2;l=r=0;
		if(a<=mij) l=query(2*nd,st,mij,segt[nd]);
		if(b>mij) r=query(2*nd+1,mij+1,dr,segt[nd]);

		if(l) return l;
		else return r;
	}
}

inline int min(int alfa,int beta)
{ return (alfa<beta)?(alfa):(beta);}

inline int max(int alfa,int beta)
{ return (alfa>beta)?(alfa):(beta);}

int main()
{
	int i,n,a1,b1,c1,na,nb,nc;
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d%d%d%d",&n,&a1,&b1,&c1);
	x.c=c1;x.p=1; 
	a=min(a1,b1);b=max(a1,b1);

//	printf("%d %d %d\n",a,b,c1);

	insert(1,1,n-1);
	for(i=2;i<n;++i)
	{
		na=(a1*i)%n;
		nb=(b1*i)%n;
		nc=(c1*i)%n;
		a1=na;b1=nb;c1=nc;

		
		x.p=i;x.c=nc; a=min(na,nb);b=max(na,nb);
//		printf("%d %d %d\n",a,b,nc);
		insert(1,1,n-1);
	}

	segt[0].c=0;segt[0].p=0;
	update(1,1,n-1);
//	for(i=1;i<=16;++i) printf("%d. %d %d\n",i,segt[i].p,segt[i].c);

	for(i=1;i<n;++i)
	{
		a=b=i;
		fprintf(out,"%d\n",query(1,1,n-1,segt[0]));
	}

	fclose(in);fclose(out);
	return 0;
}