签到题。

设 $a$ 中不同元素的个数为 $s$，若 $s$ 为奇数，易知不存在解。

考虑 $s$ 为偶数，此时定存在一种顺序使 $a$ 的前 $s$ 个元素互不相同，此时第 $s$ 个元素之后的每一个元素都已出现过，不会对元素种类产生影响，符合题意。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define len 214514
int n, a[214514], s;
map <int, bool> v;
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) { 
		cin >> a[i]; 
		if (!v[a[i]]) v[a[i]] = 1, s++;
	}
	if (s % 2) { cout << -1; return 0; }
	v.clear();
	for (int i = 1; i <= n; i++) if (!v[a[i]]) cout << a[i] << ' ', v[a[i]] = 1, a[i] = -1;
	for (int i = 1; i <= n; i++) if (a[i] != -1) cout << a[i] << ' ';
	return 0;
}

思路

设总共有 $kds$ 种。

首先考虑无解

因为 $n$ 一定是偶数，所以如果 $kds$ 是个奇数，不管你怎么排，有 $n$ 个数的数列一定是奇数种。

综上，当 $kds$ 为奇数时，直接 $-1$。

有解的情况

思路也很简单。因为我们判断了 $kds$ 为偶数，所以只需要第一次把每种都打出来一个，前面偶数个必定没问题。后面你随意，因为所有种类都输出了，你怎么搞都行。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a,b[100005],kds,mx=-1;
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a;
        mx=max(mx,a);
        if(b[a]==0)
        {
            kds++;
        }
        ++b[a];
    }
    if(kds%2==1)
    {
        cout<<-1;
        return 0;
    }
    kds=0;
    int i=1,nn=n;
    while(n>0)
    {
        if(b[i]!=0)
        {
            cout<<i<<" ";
            b[i]--;
            n--;
        }
        ++i;
        if(i>mx)
        {
            i=1;
        }
    }
    return 0;
}

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;
}