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;
	vector<vector<int>> gri(n);
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(i == j) continue;
			if(que(i, j)) gri[i].push_back(j);
		}
	}
	vector<int> c;
	for(int i = 0; i < n; ++i) if(gri[i].size() == 3) c.push_back(i);
	for(int i = 0; i < n; ++i) if(gri[i].size() == 2) c.push_back(i);
	for(int i = 0; i < n; ++i) if(gri[i].size() == 1 && gri[i][0] != c[0]) c.push_back(i);
	for(int i = 0; i < n; ++i) if(gri[i].size() == 1 && gri[i][0] == c[0]) c.push_back(i);
	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) {
	srand(300);
	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);
	}
	assert(cu.size() == 1);
	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() {
	int n, t; cin >> n >> t;
	if(n == 4) {
		cout << "0111\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: RUNTIME ERROR

Test 4

Subtask: 4

Verdict: RUNTIME ERROR