求救!!!贪心最后一个点MLE(并查集不会)
查看原帖
求救!!!贪心最后一个点MLE(并查集不会)
544756
xiaobing楼主2023/8/11 15:06
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int n, m, p, q;
int a[N];
vector<int>b[N], c[N];
priority_queue<int>q1, q2;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> p >> q;
	for (int i = 1; i <= m; i++) {
		int l = ((1LL * i * p + q) % n) + 1, r = ((1LL * i * q + p) % n) + 1;
		if (l > r)
			swap(l, r);
		b[l].push_back(i);
		c[r+1].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (!b[i].empty())
			for (auto e : b[i])
				q1.push(e);
		if (!c[i].empty())
			for (auto e : c[i])
				q2.push(e);
		while (!q2.empty() && q1.top() == q2.top())
			q1.pop(), q2.pop();
		if (q1.empty()) {
			a[i] = 0;
			continue;
		}
		a[i] = q1.top();
	}
	for (int i = 1; i <= n; i++)
		cout << a[i] << endl;
	return 0;
}
2023/8/11 15:06
加载中...