60pts, MLE#2, #8, #9, #10求助!
查看原帖
60pts, MLE#2, #8, #9, #10求助!
767099
WEXI7111楼主2023/7/5 12:31
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 2.5e7 + 10, M = 5010;
int x[N], t[N];
int mp[M][M], l[M], r[M];
int a, b, c, d;
int n, m, q;
vector<int> ans;
int X[N], Y[N];

int main()
{
    scanf("%d%d%d%d%d", &x[0], &a, &b, &c, &d);
    scanf("%d%d%d", &n, &m, &q); int K = n * m;
    for(int i = 1; i <= K; i ++) 
        t[i] = i, x[i] = (ll)(1ll * a * x[i - 1] * x[i - 1] + 1ll * b * x[i - 1] + c) % d;
    for(int i = 1; i <= K; i ++) swap(t[i], t[(x[i] % i) + 1]);
    while(q --)
    {
        int u, v; scanf("%d%d", &u, &v);
        swap(t[u], t[v]);
    }
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) 
            mp[i][j] = t[(i - 1) * m + j], X[mp[i][j]] = i, Y[mp[i][j]] = j, r[i] = m + 1;
        
    for(int k = 1; k <= K; k ++)
    {
        int xx = X[k], yy = Y[k];
        
        if(l[xx] < yy && r[xx] > yy)
        {
            ans.push_back(k);
            for(int i = 1; i < xx; i ++) r[i] = min(r[i], yy + 1);
            for(int i = xx + 1; i <= n; i ++) l[i] = max(l[i], yy - 1);
        }
    }
    
    for(int i : ans) cout << i << ' ';
}
2023/7/5 12:31
加载中...