Hamilton

#include<bits/stdc++.h>

using namespace std;

vector<string> gr;
int cnt = 0;

vector<vector<int>> mem;

bool que(int u, int v) {
	if(~mem[u][v]) return mem[u][v];
	cnt++;
	cout << "? " << u + 1 << ' ' << v + 1 << endl;
	char c; cin >> c;
	// char c = (gr[u][v] == '1' ? '>' : '<');
	mem[u][v] = c == '>';
	mem[v][u] = !mem[u][v];
	return mem[u][v];
}

void ans(vector<int> c) {
	cout << "! ";
	for(auto x : c) cout << x + 1 << ' ';
	cout << endl;
}

void solve4() {
	int n = 4;
	mem.assign(n, vector<int> (n, -1));
	vector<int> c(n);
	iota(c.begin(), c.end(), 0);
	do {
		bool ok = 1;
		for(int i = 0; i < n; ++i) {
			ok |= que(c[i], c[(i + 1) % n]);
		}
	} while(next_permutation(c.begin(), c.end()));
	ans(c);
}

vector<int> merge(vector<int> a, vector<int> b) {
	if(que(a.back(), b[0])) {
		for(auto x : b) a.push_back(x);
		return a;
	}
	else if(que(b.back(), a[0])){
		for(auto x : a) b.push_back(x);
		return b;
	}
	return {-1};
}

void solve(int n) {
	mem.assign(n, vector<int> (n, -1));
	vector<vector<int>> cu;
	for(int i = 0; i < n; ++i) cu.push_back({i});
	for(int i = 0; i + 1 < (int)cu.size(); ++i) {
		auto z = merge(cu[i], cu[i + 1]);
		if(z[0] == -1) continue;
		cu[i] = z;
		cu.erase(cu.begin() + i + 1);
	}
	for(int _ = 0; _ < 2000 && cu.size() > 1; ++_) {
		int a = rand() % (int)cu.size();
		int b = rand() % (int)cu.size();
		if(a == b) continue;
		auto z = merge(cu[a], cu[b]);
		if(z[0] == -1) continue;
		cu[a] = z;
		cu.erase(cu.begin() + b);
	}
	sort(cu.begin(), cu.end(), [&](auto a, auto b) {return a.size() > b.size(); });
	while(cu.size() > 1) {
		for(int i = 0; i < (int)cu[0].size(); ++i) {
			if(que(cu[0][i], cu.back()[0]) && que(cu.back().back(), cu[0][i + 1])) {
				while(cu.back().size()) {
					cu[0].insert(cu[0].begin() + i + 1, cu.back().back());
					cu.back().pop_back();
				}
				break;
			}
		}
		cu.pop_back();
	}
	auto c = cu[0];
	int ls = (int)c.size() - 1;
	while(que(c[0], c[ls])) ls--;

	for(int i = ls + 1; i < (int)c.size(); ++i) {
		for(int j = 0; j < i; ++j) {
			if(que(c[j], c[i]) && que(c[i], c[j + 1])) {
				c.insert(c.begin() + j + 1, c[i]);
				c.erase(c.begin() + i + 1);
				break;
			}
		}
	}
	// for(int i = 0; i < n; ++i) assert(que(c[i], c[(i + 1) % n]));
	ans(c);
}

int main() {
	srand(420);
	int n, t; cin >> n >> t;
	if(n == 4) {
		gr = {"0110", "0011", "0001", "1000"};
		cout << "0110\n0011\n0001\n1000" << endl;
		while(t--) {
			solve4();
		}
		return 0;
	}
	gr.resize(n, string(n, '0'));
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) {
			int x = rand() & 1;
			gr[i][j] = '0' + x;
			gr[j][i] = '1' - x;
		}
	}
	for(auto x : gr) cout << x << endl;
	while(t--) solve(n);
}

Test 1

Subtask:

Verdict: ACCEPTED

Test 2

Subtask: 1

Verdict: WRONG ANSWER

Test 3

Subtask: 2, 3

Verdict: ACCEPTED

Test 4

Subtask: 4

Verdict: ACCEPTED