Hamilton

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
constexpr const int T = 1e5;

random_device rd;
mt19937 g(rd());

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];
			v[i][j] = g() & 1, 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];
	};

	vector<vector<int>> V;
	for (int i = 0; i < n-1; i += 2) {
		V.push_back({i, i+1});
		if (que(i+1, i)) swap(V.back()[0], V.back()[1]);
	}
	int cnt = 0;
	auto split = [&]() -> void {
		cnt = 0;
		// int i;
		// do {
		// 	int x = g() % n;
		// 	for (int j = 0; j < (int)V.size(); j++) for (int y : V[j]) if (x == y) i = j;
		// } while (V[i].size() == 1);
		int i = g() % V.size();
		while (V[i].size() == 1) i = g() % V.size();
		vector<int> w;
		size_t x = g() % (V[i].size() - 1) + 1;
		while (V[i].size() > x) w.push_back(V[i].back()), V[i].pop_back();
		reverse(w.begin(), w.end());
		V.push_back(w);
		shuffle(V.begin(), V.end(), g);
	};
	while (1) {
		if (V.size() == 1) {
			if (que(V[0].back(), V[0].front())) break;
			split();
			split();
			continue;
		}
		if (cnt > T) {
			split();
			continue;
		}
		int i = g() % V.size(), j = i;
		while (j == i) j = g() % V.size();
		if (que(V[i].back(), V[j].front())) {
			for (int x : V[j]) V[i].push_back(x);
			V.erase(V.begin() + j);
			cnt = 0;
		}
		else cnt++;
	}
	cout << '!';
	for (int x : V[0]) cout << ' ' << x + 1;
	cout << endl;
}

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

Test 1

Subtask:

Verdict: TIME LIMIT EXCEEDED

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 2, 3

Verdict: ACCEPTED

Test 4

Subtask: 4

Verdict: ACCEPTED