记录编号	265319	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]随机数生成器	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	20.797 s
提交时间	2016-06-02 14:19:39	内存使用	191.06 MiB

#include<cstdio>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
long long last;int a,b,c,d;
int rand(){
	return last=((a*last%d+b)*last+c)%d;
}
int n,m,q,i,j;
const int NM=25000010;
int p[NM],o[NM];
int ma[5010],mi[5010];
int main()
{
	freopen("random_2014.in","r",stdin);
	freopen("random_2014.out","w",stdout);
	scanf("%d%d%d%d%d",&last,&a,&b,&c,&d);
	scanf("%d%d%d",&n,&m,&q);
	for (i=1;i<=n*m;i++) o[i]=i;
	int e,Z,u,v;
	for (i=1;i<=n*m;i++){
		rand();e=last%i+1;
		Z=o[i];o[i]=o[e];o[e]=Z;
	}
	for (i=1;i<=q;i++){
		scanf("%d%d",&u,&v);
		Z=o[u];o[u]=o[v];o[v]=Z;
	}
	for (i=1;i<=n*m;i++) p[o[i]]=i;
	
	for (i=1;i<=n;i++) ma[i]=m,mi[i]=1;
	int cnt=0;
	for (i=1;i<=n*m;i++){
		short x=(p[i]-1)/m+1,y=p[i]-(x-1)*m;
		if (mi[x]<=y&&y<=ma[x]){
			printf("%d ",i);
			cnt++;if (cnt==n+m-1) break;
			for (j=1;j<x;j++) ma[j]=min(ma[j],y);
			for (j=x+1;j<=n;j++) mi[j]=max(mi[j],y);
		}
	}
	printf("\n");
	return 0;
}