S001A. 壁垒

$\mathsf{\color{Plum}Statement}$

给定一个长度为 $n$ 的序列 $a$，是否存在一种重排方式使得每个长度为偶数的前缀，出现的数字种类数为偶数。若存在，输出方案；否则，输出 -1。

$\mathsf{\color{Plum}Solution}$

若整个序列的数字种类数为奇数，则不存在方案；否则，必定存在一种方案

• 如果整个序列的数字种类数是奇数，那么第 $n$ 位（题目中保证了 $n$ 为偶数）的数字种类数必定不是偶数
• 如果整个序列的数字种类数是偶数（令其为 $m$），那么只需将前 $m$ 个位置放置 每种数字，后面随便放置即可（这样，即可保证前 $m$ 个位置，相邻偶数位每次加 $2$，后面恒定不变）。

综上所述，即可在 $O(n)$ 的时间复杂度下 $\mathsf{\color{green} AC}$ 此题。

$\mathsf{\color{Plum}Code}$

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	unordered_map<int, int> cnt;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], cnt[a[i]] ++;

	if (cnt.size() & 1) cout << -1 << endl;
	else {
		for (auto v : cnt)
			cout << v.fi << " ";
		for (auto v : cnt) {
			int tot = v.se - 1;
			while (tot -- ) cout << v.fi << " ";
		}
		cout << endl;
	}

	return 0;
}