记录编号	144965	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]随机数生成器	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	14.942 s
提交时间	2014-12-31 23:46:31	内存使用	191.09 MiB

/*====================Asm.Def========================*/
#include <iostream>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <vector>
#include <cmath>
#include <cstring>
#ifndef DEBUG
#define getchar getchar_unlocked
#endif
using namespace std;
template <typename T>inline void getd(T &x){
	char ch = getchar();bool minus = 0;
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-'){minus = 1;ch = getchar();}
	x = ch - '0';
	while(isdigit(ch = getchar()))x = x * 10 + ch - '0';
	if(minus)x = -x;
}
/*======================================================*/
typedef long long LL;
const int maxn = 5002, maxlen = 25000003, INF = 0x3f3f3f3f;

int NM, N, M, Begin[maxn], End[maxn], A[maxlen], B[maxlen], iter;

inline void init(){
	int a, b, c, d, Q, i, j;
	getd(B[0]);getd(a);getd(b);getd(c);getd(d);
	getd(N);getd(M);getd(Q);
	NM = N * M;
	memset(End, 0x3f, sizeof(int) * (N + 2));
	for(i = 1;i <= NM;++i){
		static LL tmp;tmp = B[i-1];
		A[i] = i;
		B[i] = (tmp * tmp * a + tmp * b + c) % d;
	}
	for(i = 1;i <= NM;++i)
		swap(A[i], A[B[i] % i + 1]);
	while(Q--){
		getd(i), getd(j);
		swap(A[i], A[j]);
	}
	#define loc B
	for(i = 1;i <= NM;++i)
		loc[A[i]] = i;
}

inline bool check(int Loc, int &x, int &y){
	--Loc;
	x = Loc / M + 1, y = Loc % M + 1;
	if(y < Begin[x] || y > End[x])return 0;
	return 1;
}

inline void Set(int x, int y){
	int i;
	for(i = 1;i < x;++i)if(End[i] > y)End[i] = y;
	for(i = x+1;i <= N;++i)if(Begin[i] < y)Begin[i] = y;
}

inline void work(){
	int i, x, y;
	for(i = 1;i <= NM;++i)if(check(loc[i], x, y)){
		A[iter++] = i;
		Set(x, y);
	}
	printf("%d", A[0]);
	for(i = 1;i < iter;++i)printf(" %d", A[i]);
	putchar('\n');
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#else
		#ifndef ONLINE_JUDGE
			freopen("random_2014.in", "r", stdin);
			freopen("random_2014.out", "w", stdout);
		#endif
	#endif
	init();
	work();
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}