Cod sursa(job #86063)

Utilizator stef2nStefan Istrate stef2n Data 23 septembrie 2007 14:30:10
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Autumn Warmup 2007, Runda 2 Marime 1.81 kb
#include <cstdio>
#include <vector>
using namespace std;

#define NMAX 1000005
#define pb push_back
#define INTERV_MAX 2100000

int N,A,B,C;
vector <int> baga[NMAX];
vector <int> scoate[NMAX];
int color[NMAX];
bool ARB[INTERV_MAX];

inline int min(int x, int y)
{
	return (x<y)?x:y;
}

inline int max(int x, int y)
{
	return (x>y)?x:y;
}

void init()
{
	for(int i=1;i<=N-1;i++)
	{
		baga[min(A,B)].pb(i);
		scoate[max(A,B)].pb(i);
		color[i]=C;
		A=((long long)A*(long long)(i+1))%(long long)N;
		B=((long long)B*(long long)(i+1))%(long long)N;
		C=((long long)C*(long long)(i+1))%(long long)N;
	}
}

void build_tree(int n, int li, int ls)
{
	ARB[n]=false;
	if(li!=ls)
	{
		build_tree(2*n,li,(li+ls)/2);
		build_tree(2*n+1,(li+ls)/2+1,ls);
	}
}

void add(int n, int li, int ls, int poz)
{
	if(li==ls)
	{
		ARB[n]=true;
		return;
	}
	if(poz<=(li+ls)/2)
		add(2*n,li,(li+ls)/2,poz);
	else
		add(2*n+1,(li+ls)/2+1,ls,poz);
	ARB[n] = ARB[2*n] || ARB[2*n+1];
}

void rmv(int n, int li, int ls, int poz)
{
	if(li==ls)
	{
		ARB[n]=false;
		return;
	}
	if(poz<=(li+ls)/2)
		rmv(2*n,li,(li+ls)/2,poz);
	else
		rmv(2*n+1,(li+ls)/2+1,ls,poz);
	ARB[n] = ARB[2*n] || ARB[2*n+1];
}

int maxright(int n, int li, int ls)
{
	if(li==ls)
		return li;
	if(ARB[2*n+1])
		return maxright(2*n+1,(li+ls)/2+1,ls);
	else
		return maxright(2*n,li,(li+ls)/2);
}

void solve()
{
	for(int i=1;i<=N-1;i++)
	{
		for(vector <int>::iterator it=baga[i].begin(); it!=baga[i].end(); ++it)
			add(1,1,N-1,*it);
		if(ARB[1]==false)
			printf("0 "); // necolorat
		else
			printf("%d ",color[maxright(1,1,N-1)]);
		for(vector <int>::iterator it=scoate[i].begin(); it!=scoate[i].end(); ++it)
			rmv(1,1,N-1,*it);
	}
}


int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	scanf("%d %d %d %d",&N,&A,&B,&C);
	init();
	build_tree(1,1,N-1);
	solve();
	return 0;
}