Hamilton

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
const int T = 10;

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];
	};

	random_device rd;
	mt19937 g(rd());

	queue<vector<int>> q;
	for (int i = 0; i < n; i++) q.push({i});
	int cnt = 0;
	auto split = [&]() -> void {
		cnt = 0;
		do {
			vector<vector<int>> A;
			A.reserve(q.size());
			queue<vector<int>> tmp;
			while (q.size()) {
				auto v = q.front(); q.pop();
				if (v.size() > 1) A.push_back(v);
				else tmp.push(v);
			}
			if (A.size()) {
				shuffle(A.begin(), A.end(), g);
				vector<int> v = A.back(); A.pop_back();
				vector<int> w;
				int x = g() % (v.size() - 1) + 1;
				while ((int)v.size() > x) w.push_back(v.back()), v.pop_back();
				reverse(w.begin(), w.end());
				A.push_back(v);
				A.push_back(w);
			}
			while (tmp.size()) {
				A.push_back(tmp.front());
				tmp.pop();
			}
			shuffle(A.begin(), A.end(), g);
			for (auto y : A) q.push(y);
		}
		while (g() & 1);
	};
	while (1) {
		if (q.size() == 1) {
			auto v = q.front();
			if (que(v.back(), v.front())) break;
			split();
			continue;
		}
		if (cnt >= T) {
			split();
			continue;
		}
		auto v = q.front(); q.pop();
		auto w = q.front(); q.pop();
		if (que(v.back(), w.front())) {
			for (int x : w) v.push_back(x);
			q.push(v);
			cnt = 0;
		}
		else {
			cnt++;
			q.push(v);
			q.push(w);
		}
	}
	cout << '!';
	for (int x : q.front()) 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: ACCEPTED