Hamilton

#include<bits/stdc++.h>

using namespace std;

vector<string> gr;
int cnt = 0;

// vector<int> perm;
vector<vector<int>> mem;

bool que(int u, int v) {
	// u = perm[u], v = perm[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;
}

int ran(int a, int b) {
    static std::random_device rd;  // a seed source for the random number engine
    static std::mt19937 gen(rd()); // mersenne_twister_engine seeded with rd()
    std::uniform_int_distribution<> distrib(a, b);
    return distrib(gen);
}

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]);
		}
		if(ok) {
			ans(c);
			return;
		}
	} while(next_permutation(c.begin(), c.end()));
}

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 = ran(0, (int)cu.size() - 1);
		int b = ran(0, (int)cu.size() - 1);
		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--;
	ls++;
	if(ls < n) {
		for(int i = 0; i < ls; ++i) {
			if(que(c[i], c[ls]) && que(c.back(), c[i + 1])) {
				for(int j = 0; j < (int)c.size() - ls; ++j) {
					c.insert(c.begin() + i + 1, c.back());
					c.pop_back();
				}
				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;
	// perm.resize(n);
	// iota(perm.begin(), perm.end(), 0);
	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 = 0; j < n; ++j) {
			if(i == j) continue;
			int x = ran(0, 1);
			gr[i][j] = '1' - x;
			gr[j][i] = '0' + x;
		}
	}
	for(auto x : gr) cout << x << endl;
	while(t--) solve(n);
	// cerr << cnt << '\n';
}

Test 1

Subtask:

Verdict: ACCEPTED

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 2, 3

Verdict: ACCEPTED

Test 4

Subtask: 4

Verdict: ACCEPTED