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(0), F(0);
	vector<int> od(n); iota(od.begin(), od.end(), 0);
	shuffle(od.begin(), od.end(), g);
	for (int i = 0; i < n-1; i += 2) {
		V.push_back({od[i], od[i+1]});
		if (que(od[i+1], od[i])) swap(V.back()[0], V.back()[1]);
	}
	vector<int> v;
	v = V.back(); V.pop_back();
	shuffle(V.begin(), V.end(), g);

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

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 2, 3

Verdict: ACCEPTED

Test 4

Subtask: 4

Verdict: ACCEPTED