Cod sursa(job #534634)

Utilizator AndreyPAndrei Poenaru AndreyP Data 15 februarie 2011 22:03:36
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#define N 1000010

int n;
int a[N],b[N],c[N];
int rez[N];
int t[N];

inline void citire() {
	scanf("%d%d%d%d",&n,&a[1],&b[1],&c[1]);
	
	for(int i=2; i<n; ++i) {
		a[i] = (a[i-1]*i) % n;
		b[i] = (b[i-1]*i) % n;
		c[i] = (c[i-1]*i) % n;
		t[i] = i;
	}
	t[1] = 1;
	t[n] = n;
}

inline int find(int x) {
	int ret = x;	
	while(ret!=t[ret])
		ret = t[ret];	
	int y;	
	while(x!=ret) {
		y = t[x];
		t[x] = ret;
		x = y;
	}
	return ret;
}

inline void unite(int x,int y) {
	x = find(x);
	y = find(y);
	
	if(y>x)
		t[x] = y;
	else
		t[y] = x;
}

inline void rezolva() {
	int st,dr;
	for(int i=n-1; i>0; --i) {
		if(a[i]<=b[i]) {
			st = a[i];
			dr = b[i];
		} else {
			st = b[i];
			dr = a[i];
		}
		
		st = find(st);
		for(; st<=dr; st=find(st)) {
			rez[st] = c[i];
			unite(st,st+1);
		}
	}
}

inline void scrie() {
	for(int i=1; i<n; ++i)
		printf("%d\n",rez[i]);
}

int main() {
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	
	citire();
	rezolva();
	scrie();
	
	return 0;
}