Hamilton

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
mt19937 mt(time(0));

// --- JUDGE ---

ll judge_query_count;
vector<vector<bool>> judge_graph;

void judge_init(ll n) {
    judge_query_count = 0;
    judge_graph = vector<vector<bool>>(n, vector<bool>(n));
    for (ll i = 0; i < n; i++) {
        for (ll j = i+1; j < n; j++) {
            bool ij = (j - i + n) % n <= n/2;
            judge_graph[i][j] = ij;
            judge_graph[j][i] = !ij;
        }
    }

    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (i == j) cout << "0";
            else cout << judge_graph[i][j];
        }
        cout << endl;
    }
}

// true iff u -> v (1-indexed)
bool judge_query(ll u, ll v) {
    assert(u != v);
    judge_query_count++;
    cout << "? " << u << ' ' << v << endl;
    char ans; cin >> ans;
    return ans == '>';
}

// --- CONTESTANT ---

map<pair<ll, ll>, bool> mem;
bool ask(ll u, ll v) {
    if (u > v) return !ask(v, u);
    if (mem.count({u, v})) return mem[{u, v}];
    return mem[{u, v}] = judge_query(u+1, v+1);
}

ll stat = 0;

void solve(ll n) {
    mem.clear();

    // initialize length 2 paths
    vector<vector<ll>> paths;
    for (ll i = 0; i < n/2; i++) {
        if (ask(2*i, 2*i+1)) paths.push_back({2*i, 2*i+1});
        else paths.push_back({2*i+1, 2*i});
    }
    if (n & 1) paths.push_back({n-1});

    auto split_random_path = [&]() {
        ll i;
        do i = mt() % sz(paths);
        while (sz(paths[i]) < 2);
        ll k = 1 + mt() % (sz(paths[i]) - 1);
        paths.emplace_back(paths[i].begin() + k, paths[i].end());
        paths[i].erase(paths[i].begin() + k, paths[i].end());
    };

    ll bs = 1e9;
    vector<vector<ll>> buf;
    while (sz(paths) > 1) {
        ll i = 0;
        ll j = 1+mt()%(sz(paths)-1);
        if (bs < sz(paths)) j = bs+mt()%(sz(paths)-bs);
        if (ask(paths[i].back(), paths[j][0])) {
            paths[i].insert(paths[i].end(), all(paths[j]));
            paths.erase(paths.begin() + j);
            bs = sz(paths);
            paths.insert(paths.begin(), all(buf));
            buf.clear();
        }
        else {
            buf.push_back(paths[j]);
            paths.erase(paths.begin() + j);
        }
    }
    paths.insert(paths.begin(), all(buf));
    buf.clear();
    stat += sz(paths);
    ll bad_iterations = 0;
    merge_paths:
    while (sz(paths) > 1) {
        ll i = mt() % sz(paths);
        ll j = mt() % sz(paths);
        if (i == j) continue;
        if (ask(paths[i].back(), paths[j][0])) {
            paths[i].insert(paths[i].end(), all(paths[j]));
            paths.erase(paths.begin() + j);
        }
        else if (++bad_iterations % (2*n) == 0) {
            split_random_path();
        }
    }
    if (!ask(paths[0].back(), paths[0][0])) {
        split_random_path();
        split_random_path();
        goto merge_paths;
    }

    // verify correctness
    for (ll i = 0; i+1 < n; i++) {
        assert(ask(paths[0][i], paths[0][i+1]));
    }
    assert(ask(paths[0].back(), paths[0][0]));
    
    cout << "!";
    for (auto &e : paths[0]) cout << ' ' << e+1;
    cout << endl;
}

// --- TESTS ---

int main() {
    ll n, t; cin >> n >> t;
    judge_init(n);
    for (ll i = 0; i < t; i++) {
        solve(n);
    }
    cerr << (double)stat / t << endl;
}

Test 1

Subtask:

Verdict: ACCEPTED

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 2, 3

Verdict: ACCEPTED

Test 4

Subtask: 4

Verdict: ACCEPTED