Submission #37039146

---

Source Code Expand

/*
 * File created on 12/05/2022 at 09:18:25.
 * Link to problem: 
 * Description: 
 * Time complexity: O()
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2022 Francois Vogel
*/

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define sz(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<vi> graph;
vector<pii> b;

void dfs(vi& path, int x, int p = -1) {
    for (int y : graph[x]) if (y != p) {
        path.pb(b[x].f);
        dfs(path, y, x);
    }
    for (int i = 0; i < b[x].s+1-sz(graph[x])-(p == -1 ? 1 : 0); i++) {
        path.pb(b[x].f);
    }
}

void solve() {
    int n;
    cin >> n;
    map<int, int> m;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (!m.count(x)) m[x] = 0;
        m[x]++;
    }
    b = vector<pii>(all(m));
    sort(all(b), [](pii a, pii b) { return a.s > b.s; });
    if (n >= 2*sz(b)-2) {
        graph = vector<vi>(sz(b));
        int at = 0;
        for (int i = 1; i < sz(b); i++) {
            while (sz(graph[at]) == b[at].s) at++;
            assert(at < i);
            assert(sz(graph[at]) < b[at].s);
            graph[at].pb(i);
            graph[i].pb(at);
        }
        vi path;
        dfs(path, 0);
        assert(sz(path) == n);
        for (int x : path) cout << x << ' ';
    }
    else {
        for (auto i : b) {
            for (int j = 0; j < i.s; j++) {
                cout << i.f << " ";
            }
        }
    }
    cout << '\n';
}

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

    int n;
    cin >> n;
    while (n--) solve();

    cout.flush();
    int d = 0;
    d++;
}

Submission Info

Judge Result