https://csacademy.com/contest/round-19/#task/smallest-array-permutation

$N$個の要素を持つ配列が与えられる．同じ要素が隣り合わず，辞書順で最小のものを求める．

辞書順最小にしたいので，小さい数から順番に並べたいが，前回置いたものと同じ数を置くことは出来ないため，前回置いた数以外の最小の数を並べていく．同じ数が隣り合わないために，まだ決めていない要素数が奇数の時かつ，同じ要素が$\frac{要素数+1}{2}$ある時は，$1$個飛ばしで並べなければならないことに注意する．

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
	int n;
	cin >> n;

	map<int, int> m;
	rep(i, n) {
		int x;
		cin >> x;

		m[x]++;
	}

	priority_queue<P> que;
	each(it, m) {
		if(it->second > (n + 1) / 2) {
			cout << -1 << endl;
			return 0;
		}

		que.push(mp(it->se, -it->fi));
	}

	int len = n, pre = -1;
	vector<int> ans;

	while(que.size()) {
		int cnt = que.top().fi;
		int id = -que.top().se;

		while(m.count(id) == 0) {
			que.pop();
			cnt = que.top().fi;
			id = -que.top().se;
		}

		while(true) {
			cnt = m[id];
			que.pop();

			if(!que.size()) break;

			if(que.top().fi <= cnt) {
				que.push(mp(cnt, -id));
				break;
			} else {
				cnt = que.top().fi;
				id = -que.top().se;
			}
		}

		if(len % 2 == 1) {
			if(cnt == (len + 1) / 2) {
				m[id]--;
				if(m[id] == 0) m.erase(id);

				pre = id;
				ans.push_back(id);
				que.push(mp(cnt - 1, -id));
			} else {
				map<int, int>::iterator it = m.begin();

				if(it->fi == pre) it++;
				m[it->fi]--;
				if(m[it->fi] == 0) m.erase(it->fi);

				pre = it->fi;
				ans.push_back(it->fi);
			}
		} else {
			map<int, int>::iterator it = m.begin();
			if(it->fi == pre) it++;
			m[it->fi]--;
			if(m[it->fi] == 0) m.erase(it->fi);

			pre = it->fi;
			ans.push_back(it->fi);
		}

		len--;
		if(len == 0) break;
	}

	rep(i, ans.size()) {
		if(i) cout << " ";
		cout << ans[i];
	}
	cout << endl;

	return 0;
}