#include #include #include #include #include #include #include using namespace std; bool interactive = true; pair diff(int x, int y, int n) { int p = x / n - y / n, q = x % n - y % n; if (p > q) swap(p, q); return {p, q}; } int n = -1; int qcount = 0; vector ans; template void random_shuffle(vector &a) { mt19937 mt{ random_device{}() }; for (int i = a.size() - 1; i >= 1; i--) { uniform_int_distribution dist(0, i); int j = dist(mt); if (i != j) swap(a[i], a[j]); } } void initialize_ans(int size) { n = size; ans.resize(n * n - n); iota(ans.begin(), ans.end(), n); random_shuffle(ans); // ans = {3, 5, 6, 8, 4, 7}; cerr << "initialize with size = " << size << endl; cerr << "ans ="; for (int x : ans) cerr << ' ' << x; cerr << endl; } int getsize() { int tmp; cin >> tmp; if (cin.eof()) { interactive = false; initialize_ans(10); return n; } return n = tmp; } pair query(int i, int j) { if (!interactive) { ++qcount; assert(qcount <= (n * n - n) / 2 * 3); auto [p, q] = diff(ans[i], ans[j], n); cerr << "? " << i << ' ' << j << endl; cerr << p << ' ' << q << endl; return {p, q}; } else { cout << "? " << i+1 << ' ' << j+1 << endl; int x, y; cin >> x >> y; return {x, y}; } } void answer(vector& r) { if (!interactive) { cerr << '!'; for (int x : r) cerr << ' ' << x; cerr << endl; assert(r.size() == n * n - n); for (int i = 0; i < r.size(); i++) { assert(r[i] == ans[i]); } } else { cout << '!'; for (int x : r) cout << ' ' << x; cout << endl; } } int main() { int n = getsize(); vector > res(n*n-n); vector ans(n*n-n, 0); for (int i = 1; i < n * n - n; i++) { res[i] = query(0, i); } auto sum = [](pair x) { return x.first + x.second; }; auto cmp = [sum](pair x, pair y) { return sum(x) < sum(y); }; int idx10 = max_element(res.begin(), res.end(), cmp) - res.begin(); if (sum(res[idx10]) < 0) idx10 = 0; int idxnn = min_element(res.begin(), res.end(), cmp) - res.begin(); if (sum(res[idxnn]) > 0) idxnn = 0; // cerr << idx10 << ' ' << idxnn << endl; if (idx10 == 0) ans[0] = n; else if (idxnn == 0) ans[0] = n * n - 1; else { for (int x = n; x < n * n; x++) if (diff(x, n, n) == res[idx10] && diff(x, n * n - 1, n) == res [idxnn]) { assert(ans[0] == 0); ans[0] = x; } } // cerr << "a[0] = " << ans[0] << endl; map, vector > idx_of; for (int i = 1; i < n * n - n; i++) idx_of[res[i]].push_back(i); for (auto &[k, v] : idx_of) { auto [p, q] = k; // cerr << p << ' ' << q << " =>"; // for (int x : v) cerr << ' ' << x; // cerr << endl; } for (auto &[k, v] : idx_of) { auto [p, q] = k; int a0 = ans[0] / n - p, a1 = ans[0] % n - q, b0 = ans[0] / n - q, b1 = ans[0] % n - p; auto ok = [n](int x) { return 0 <= x && x < n; }; int a = ok(a0) && ok(a1) ? (ans[0] / n - p) * n + (ans[0] % n - q) : -1, b = ok(b0) && ok(b1) ? (ans[0] / n - q) * n + (ans[0] % n - p) : -1; if (v.size() == 1) { const int i = v[0]; // cerr << p << ' ' << q << ' ' << i << ' ' << a << ' ' << b << endl; if (n <= a && a < n * n) { assert(k == diff(ans[0], a, n)); ans[i] = a; } else { assert(n <= b && b < n * n); assert(k == diff(ans[0], b, n)); ans[i] = b; } assert(k == diff(ans[0], ans[i], n)); } else { assert(v.size() == 2); int i = v[0], j = v[1]; // cerr << p << ' ' << q << ' ' << i << ' ' << j << endl; assert(n <= a && a < n * n); assert(n <= b && b < n * n); assert(a != b); assert(k == diff(ans[0], a, n)); assert(k == diff(ans[0], b, n)); if (diff(a, n, n) != diff(b, n, n)) { if (query(i, idx10) == diff(a, n, n)) { ans[i] = a; ans[j] = b; } else { ans[j] = a; ans[i] = b; } } else { assert(diff(a, n * n - 1, n) != diff(b, n * n - 1, n)); if (query(i, idxnn) == diff(a, n * n - 1, n)) { ans[i] = a; ans[j] = b; } else { ans[j] = a; ans[i] = b; } } } } answer(ans); }