#include #include #include #include #include #include #include #include #include // #define DEBUG #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; typedef pair P; class Simulator{ public: Simulator(int _n){ random_device seed_gen; mt19937 engine(seed_gen()); n = _n; m = n*(n-1); vector v; for(int i = 1; i <= n-1; i++){ for(int j = 0; j <= n-1; j++){ v.push_back(i*n+j); } } shuffle(v.begin(), v.end(), engine); for(int i : v){ x.push_back(i/n); y.push_back(i%n); } } int n; int m; int query_count = 0; vector x; vector y; // queryは1-indexed P query(int i, int j){ query_count++; assert(query_count <= 3*(n*(n-1))/2); i--; j--; int p = x[i]-x[j]; int q = y[i]-y[j]; if(p > q) swap(p, q); return P(p, q); } bool verify(vector ans){ assert(ans.size() == m); for(int i = 0; i < m; i++){ if(ans[i] != x[i]*n+y[i]) return false; } return true; } void print_correct_ans(){ for(int i = 0; i < m; i++) cout << x[i]*n+y[i] << ' '; cout << endl; } }; int n; bool is_in_field(int x, int y){ return x >= 1 && x <= n-1 && y >= 0 && y <= n-1; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> n; #ifdef DEBUG Simulator sim(n); #endif int m = n*(n-1); vector sum(m+1), vp(m+1), vq(m+1); int min_sum = 100000, min_sum_idx = -1; int max_sum = -100000, max_sum_idx = -1; map> mp; for(int i = 2; i <= m; i++){ int p, q; #ifdef DEBUG auto x = sim.query(i, 1); p = x.first; q = x.second; #else cout << "? " << i << ' ' << 1 << endl; cin >> p >> q; #endif vp[i] = p; vq[i] = q; sum[i] = p+q; mp[P(p, q)].push_back(i); if(max_sum < sum[i]){ max_sum = sum[i]; max_sum_idx = i; } if(min_sum > sum[i]){ min_sum = sum[i]; min_sum_idx = i; } } vector ans_x(m+1), ans_y(m+1); if(min_sum < 0) { ans_x[min_sum_idx] = 1; ans_y[min_sum_idx] = 0; } if(max_sum > 0) { ans_x[max_sum_idx] = n-1; ans_y[max_sum_idx] = n-1; } if(min_sum > 0){ ans_x[1] = 1; ans_y[1] = 0; }else if(max_sum < 0){ ans_x[1] = n-1; ans_y[1] = n-1; }else if(vp[max_sum_idx]-vp[min_sum_idx] == n-1 || vq[max_sum_idx]-vp[min_sum_idx] == n-1){ ans_y[1] = -vp[min_sum_idx]; ans_x[1] = 1-vq[min_sum_idx]; }else if(vp[max_sum_idx]-vq[min_sum_idx] == n-1 || vq[max_sum_idx]-vq[min_sum_idx] == n-1){ ans_y[1] = -vq[min_sum_idx]; ans_x[1] = 1-vp[min_sum_idx]; }else{ throw ""; } for(auto i : mp){ int p = i.first.first; int q = i.first.second; auto v = i.second; int x1 = ans_x[1]+p; int y1 = ans_y[1]+q; int x2 = ans_x[1]+q; int y2 = ans_y[1]+p; if(v.size() == 1){ if(is_in_field(x1, y1)) { ans_x[v[0]] = x1; ans_y[v[0]] = y1; }else{ assert(is_in_field(x2, y2)); ans_x[v[0]] = x2; ans_y[v[0]] = y2; } continue; } int s = -1, t = -1; // (1, 0)では区別がつかないので(n-1, n-1)を投げる if(ans_x[1]-ans_y[1] == 1){ #ifdef DEBUG auto x = sim.query(v[0], max_sum_idx); s = x.first; t = x.second; #else cout << "? " << v[0] << ' ' << max_sum_idx << endl; cin >> s >> t; #endif int s_sim = min(x1-(n-1), y1-(n-1)); int t_sim = max(x1-(n-1), y1-(n-1)); if(s_sim == s && t_sim == t){ ans_x[v[0]] = x1; ans_y[v[0]] = y1; ans_x[v[1]] = x2; ans_y[v[1]] = y2; }else{ ans_x[v[0]] = x2; ans_y[v[0]] = y2; ans_x[v[1]] = x1; ans_y[v[1]] = y1; } }else{ #ifdef DEBUG auto x = sim.query(v[0], min_sum_idx); s = x.first; t = x.second; #else cout << "? " << v[0] << ' ' << min_sum_idx << endl; cin >> s >> t; #endif int s_sim = min(x1-1, y1); int t_sim = max(x1-1, y1); if(s_sim == s && t_sim == t){ ans_x[v[0]] = x1; ans_y[v[0]] = y1; ans_x[v[1]] = x2; ans_y[v[1]] = y2; }else{ ans_x[v[0]] = x2; ans_y[v[0]] = y2; ans_x[v[1]] = x1; ans_y[v[1]] = y1; } } } #ifdef DEBUG cout << min_sum_idx << ' ' << max_sum_idx << endl; vector ans; for(int i = 1; i <= m; i++){ ans.push_back(ans_x[i]*n+ans_y[i]); } if(sim.verify(ans)){ cout << "OK" << endl; }else{ cout << "NG" << endl; } cout << "! "; sim.print_correct_ans(); #endif cout << "! "; for(int i = 1; i <= m; i++) cout << ans_x[i]*n+ans_y[i] << ' '; cout << endl; }