这个题有毒emmm 卡常数真是难受QAQ
首先我们按照题目的方式产生随机数,然后按照题目描述的方式打乱即可。
接下来我们维护每一行的可行区域,贪心地寻找路径即可。
关于卡时间:
1. 拿个数组把随机数存起来比现生成现用来得快,我也不知道为什么
2. 注意到可行区域的边界坐标有单调性,及时退出循环可以减少运行时间。
3. %能省则省。
4. ~~开个O2~~
```cpp
extern "C" {
int scanf(const char*,...);
int printf(const char*,...);
}
#define maxn 25000010
#define Lovelive long long
int T[maxn], P[maxn], L[5010], R[5010];
int main() {
Lovelive l;
int a, b, c, d;
int n, m, q, t, u, v, x = 0, y = 0, sqr;
scanf("%lld%d%d%d%d%d%d%d", &l, &a, &b, &c, &d, &n, &m, &q);
sqr = n * m;
for(register int i = 0; i != sqr; ++i) T[i] = i, l = P[i] = ((a * l + b) * l + c) % d;
for(register int i = 0; i != sqr; ++i) l = P[i] % (i+1), t = T[l], T[l] = T[i], T[i] = t;
for(int i = 0; i != q; ++i) scanf("%d%d", &u, &v), t = T[u-1], T[u-1] = T[v-1], T[v-1] = t;
for(register int i = 0; i != sqr; ++i) P[T[i]] = i;
for(int i = 0; i != n; ++i) R[i] = m - 1;
for(register int i = 0; i != sqr; ++i) {
x = P[i] / m, y = P[i] - x * m;
if(L[x] <= y && y <= R[x]) {
printf("%d ", i + 1);
for(int k = x-1; k >= 0; --k) {
if(y < R[k]) R[k] = y;
else break;
}
for(int k = x+1; k != n; ++k) {
if(y > L[k]) L[k] = y;
else break;
}
}
}
return 0;
}
```