Hamilton

input/code.cpp: In function 'void solve()':
input/code.cpp:34:14: warning: variable 'rebuild' set but not used [-Wunused-but-set-variable]
   34 |         auto rebuild = [&]() -> void {
      |              ^~~~~~~

#include <bits/stdc++.h>

using namespace std;

int n;

void gen() {
	vector<vector<bool>> v(n, vector<bool>(n, 0));
	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
			v[i][j] = (n + i - j) % n <= (n + j - i) % n, v[j][i] = !v[i][j];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cout << v[i][j];
		cout << endl;
	}
}

void solve() {
	vector<vector<int>> Q(n, vector<int>(n, -1));
	auto que = [&](int i, int j) -> bool {
		assert (i != j);
		if (~Q[i][j]) return Q[i][j];
		cout << "? " << i + 1 << ' ' << j + 1 << endl;
		char c; cin >> c;
		Q[i][j] = c == '>';
		Q[j][i] = !Q[i][j];
		return Q[i][j];
	};
	int cnt = 0;
	queue<pair<int, vector<int>>> q;

	random_device rd;
	mt19937 g(rd());
	auto rebuild = [&]() -> void {
		vector<vector<int>> A;
		A.reserve(q.size());
		while (q.size()) {
			auto [_, v] = q.front(); q.pop();
			A.push_back(v);
		}
		shuffle(A.begin(), A.end(), g);
		vector<int> v = A.back(); A.pop_back();
		int s = g() % (v.size() + 1);
		vector<int> L, R;
		for (int i = 0; i < (int)v.size(); i++) (i < s ? L : R).push_back(v[i]);
		if (L.size()) A.push_back(L);
		if (R.size()) A.push_back(R);
		shuffle(A.begin(), A.end(), g);
		cnt = 0;
		for (auto w : A) q.push({cnt-1, w});
	};

	while (1) {
		while (q.size()) q.pop();
		cnt = 0;
		vector<int> od(n);
		iota(od.begin(), od.end(), 0);
		shuffle(od.begin(), od.end(), g);
		for (int i : od) q.push({cnt-1, vector<int>(1, i)});
		while (q.size() > 1) {
			auto [i, v] = q.front(); q.pop();
			auto [j, w] = q.front(); q.pop();
			if (j >= cnt) break;
			// if (j >= cnt) {
			// 	q.push({i, v});
			// 	q.push({j, w});
			// 	rebuild();
			// 	continue;
			// }
			if (que(v.back(), w.front())) {
				for (int x : w) v.push_back(x);
				q.push({cnt++, v});
			}
			else if (que(w.back(), v.front())) {
				for (int x : v) w.push_back(x);
				q.push({cnt++, w});
			}
			else {
				if (g() & 1) swap(v, w);
				q.push({cnt, v});
				q.push({cnt, w});
			}
		}
		if (q.size() != 1) continue;
		auto [_, v] = q.front();
		if ((int)v.size() != n) continue;
		if (que(v.back(), v.front())) break;
		// rebuild();
	}
	cout << '!';
	for (int x : q.front().second) cout << ' ' << x + 1;
	cout << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> n >> t;
	gen();
	while (t--) solve();
}

Test 1

Subtask:

Verdict: ACCEPTED

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 2, 3

Verdict: ACCEPTED

Test 4

Subtask: 4

Verdict: WRONG ANSWER