Hamilton

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

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];
	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 {
		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<pair<int, int>> S;
	for (int i = 0; i < n-1; i += 2) {
		S.push_back({i, i+1});
		if (que(i+1, i)) swap(S.back().first, S.back().second);
	}
	vector<int> v;
	v.push_back(S[0].first);
	v.push_back(S[0].second);
	vector<int> V;
	for (int i = 1; i < (int)S.size(); i++) V.push_back(i);
	int F = -1;

	while ((int) v.size() < n) {
		if (~F && que(v.back(), S[F].first)) {
			v.push_back(S[F].first);
			v.push_back(S[F].second);
			V.erase(find(V.begin(), V.end(), F));
			F = -1;
		}
		shuffle(V.begin(), V.end(), g);
		bool b = 0;
		for (int i : V) {
			if (que(v.back(), S[i].first)) {
				b = 1;
				v.push_back(S[i].first);
				v.push_back(S[i].second);
				V.erase(find(V.begin(), V.end(), i));
				break;
			}
			else F = i;
		}
		if (!b) break;
	}
	if ((int) v.size() < n || !que(v.back(), v.front())) {
		vector<vector<int>> Z = { v };
		for (int i : V) Z.push_back({S[i].first, S[i].second});
		int cnt = 0;
		auto split = [&]() -> void {
			cnt = 0;
			int m = Z.size();
			int i = g() % m;
			while (Z[i].size() == 1) i = g() % m;
			int x = g() % (Z[i].size() - 1) + 1;
			Z.emplace_back(Z[i].begin() + x, Z[i].end());
			Z[i].erase(Z[i].begin() + x, Z[i].end());
		};
		while (1) {
			if (Z.size() == 1) {
				if (que(Z[0].back(), Z[0].front())) break;
				split();
				split();
				continue;
			}
			if (cnt > 2 * n) {
				split();
				continue;
			}
			int i = g() % Z.size(), j = i;
			while (j == i) j = g() % Z.size();
			if (que(Z[i].back(), Z[j].front())) {
				for (int x : Z[j]) Z[i].push_back(x);
				Z.erase(Z.begin() + j);
				cnt = 0;
			}
			else cnt++;
		}
		v = Z[0];
	}
	cout << '!';
	for (int x : v) 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: WRONG ANSWER

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 2, 3

Verdict: ACCEPTED

Test 4

Subtask: 4

Verdict: ACCEPTED