提出 #37046270

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double PI = acos(-1);



int main() {
    int t;
    cin >> t;
    rep(ti,t) {
        int n;
        cin >> n;
        vector<int> cnt(n);
        rep(i,n) {
            int x;
            cin >> x;
            x--;
            cnt[x] += 1;
        }
        int k = 0;
        rep(i,n) {
            if (cnt[i] > 0) {
                k += 1;
            }
        }
        if (k >= 3 && n >= 2 * (k - 1)) {
            int sum = n;
            vector<int> extra(n, 0);
            set<pair<int, int>> s;
            rep(i,n) {
                if (cnt[i] > 0) {
                    while (sum > 2 * (k - 1) && cnt[i] > 1) {
                        cnt[i] -= 1;
                        extra[i] += 1;
                        sum -= 1;
                    }
                    s.emplace(cnt[i], i);
                }
            }
            vector<vector<int>> g(n);
            rep(i,k-1) {
                int x = s.begin()->second;
                int y = prev(s.end())->second;
                g[x].push_back(y);
                g[y].push_back(x);
                s.erase(s.begin());
                s.erase(prev(s.end()));
                cnt[y] -= 1;
                s.emplace(cnt[y], y);
            }
            vector<int> ans;
            rep(i,n) {
                if (cnt[i] > 0) {
                    function<void(int, int)> dfs = [&](int v, int p) {
                        rep(j,extra[v]+1) {
                            ans.push_back(v);
                        }
                        for (int u : g[v]) {
                            if (u == p) continue;
                            dfs(u, v);
                            ans.push_back(v);
                        }
                    };
                    dfs(i, -1);
                    break;
                }
            }
            rep(i,n) {
                cout << ans[i] + 1 << " \n"[i == n-1];
            }
        } else {
            vector<int> ans;
            rep(i,n) {
                rep(j,cnt[i]) {
                    ans.push_back(i);
                }
            }
            rep(i,n) {
                cout << ans[i] + 1 << " \n"[i == n - 1];
            }
        }
    }
    return 0;
}

提出情報

ジャッジ結果