Hamilton

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

	random_device rd;
	mt19937 g(rd());

	vector<vector<vector<int>>> H(1);
	for (int i = 0; i < n; i++) H[0].push_back({ i });
	while (1) {
		auto v = H.back();
		if (v.size() == 1) {
			if (que(v[0].back(), v[0].front())) break;
			while (H.size() > 1 && g() & 1) H.pop_back();
			continue;
		}
		shuffle(v.begin(), v.end(), g);
		int m = v.size();
		bool b = 1;
		for (int i = 0; i < m && b; i++) for (int j = 0; j < m && b; j++) if (i != j) if (que(v[i].back(), v[j].front())) {
			vector<int> w = v[i];
			for (int x : v[j]) w.push_back(x);
			v.push_back(w);
			if (i > j) v.erase(v.begin() + i);
			v.erase(v.begin() + j);
			if (i < j) v.erase(v.begin() + i);
			H.push_back(v);
			b = 0;
		}
		if (b) {
			while (H.size() > 1 && g() & 1) H.pop_back();
		}
	}
	cout << '!';
	for (int x : H.back()[0]) cout << ' ' << x + 1;
	cout << endl;

//	auto f = [&](auto&& self, vector<vector<int>> v) -> bool {
//		if (v.size() == 1) {
//			if (que(v[0].back(), v[0].front())) {
//				cout << '!';
//				for (int x : v[0]) cout << ' ' << x + 1;
//				cout << endl;
//				return 1;
//			}
//			return 0;
//		}
//		int m = v.size();
//		for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) if (i != j) if (que(v[i].back(), v[j].front())) {
//			auto tmp = v;
//			vector<int> w = v[i];
//			for (int x : v[j]) w.push_back(x);
//			tmp.push_back(w);
//			if (i > j) tmp.erase(tmp.begin() + i);
//			tmp.erase(tmp.begin() + j);
//			if (i < j) tmp.erase(tmp.begin() + i);
//			if (self(self, tmp)) return 1;
//		}
//		return 0;
//	};
//	f(f, v);
}

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: TIME LIMIT EXCEEDED