UOJ Easy Round #11 T2 科考工作 Sol

感谢 @mfeitveer 提供的思路。

昨天没听懂，今天想明白了。

大概是这样的，把众数取出来，然后把整个数组减掉众数（任意一个都行）。

拎出来众数以外的数，进行随机打乱。

然后枚举 \(i\)，计算前缀和模 \(n\) 的余数，存储起来。

如果发现出现过相同的余数（设为 \([1,j]\)），那么 \([i+1,j]\) 内的元素就模 \(n\) 余 \(0\)。

把众数补上去（因为减掉之后为 \(0\)）了，如果合法就输出答案。

反复随机打乱即可 AC（）。

#include <bits/stdc++.h>
using namespace std;

const int N = 6e5 + 10;
int n, _n, a[N], cnt[N];
vector <pair <int, int> > g;
unordered_map <int, int> Map;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n; _n = 2 * n - 1;
	for (int i = 1; i <= _n; ++i) cin >> a[i], ++cnt[a[i]];
	int d = n; for (int i = 0; i < n; ++i) if (cnt[i] > cnt[d]) d = i;
	if (cnt[d] >= n) {
		for (int i = 1, ct = 0; i <= _n; ++i) {
			if (a[i] == d) cout << i << ' ', ++ct;
			if (ct == n) break;
		}
		return cout << endl, 0;
	}
	for (int i = 1; i <= _n; ++i) if (a[i] ^ d) g.push_back({i, (a[i] - d + n) % n});
	while (1) {
		Map.clear(); int sum = 0, ct = 0;
		for (auto [id, val]: g) {
			(sum += val) %= n, ++ct; int &kel = Map[sum];
			if (kel) {
				if (!(ct - kel + cnt[d] >= n && ct - kel <= n)) continue;
				vector <int> res; for (int i = kel; i < ct; ++i) res.emplace_back(g[i].first);
				for (int i = 1; i <= _n; ++i) {
					if (res.size() == n) break;
					if (a[i] ^ d) continue; res.emplace_back(i);
				}
				for (auto to: res) cout << to << ' ';
				return cout << endl, 0;
			}
			kel = ct;
		}
		random_shuffle(g.begin(), g.end());
	}
	return 0;
}