#include using namespace std; #define rep(i,a,b) for(auto i = (a); i < (b); i++) #define pb push_back #define fs first #define sc second typedef long long ll; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; typedef vector vvii; typedef pair iiii; typedef pair i8; const double EPS = 1e-9; vi BOARD; vi ANS; int quest = 0; void ans(vi A) { cout << "!"; for(auto a : A) cout << " " << a; cout << endl; } ii ask(int i, int j) { quest++; assert(i != j); cout << "? " << i << " " << j << endl; int a,b; cin >> a >> b; return ii(a,b); } iiii get(int i, int j) { ii t = ask(i+1, j+1); return iiii(ii(i,j), t); } int share(iiii a, iiii b) { if(a.sc.fs == b.sc.fs) return a.sc.fs; if(a.sc.fs == b.sc.sc) return a.sc.fs; if(a.sc.sc == b.sc.fs) return a.sc.sc; if(a.sc.sc == b.sc.sc) return a.sc.sc; return 0; } // (index1,index2), (value1, value2) // assume never x y x y iiii join(iiii a, iiii b) { if(a.sc.fs == a.sc.sc) { // set ANS[a.fs.sc] = a.sc.fs; ANS[a.fs.fs] = a.sc.fs; return b; } else if(b.sc.fs == b.sc.sc) { ANS[b.fs.sc] = b.sc.fs; ANS[b.fs.fs] = b.sc.fs; return a; } // Very special case if(min(a.sc.fs, a.sc.sc) == min(b.sc.fs, b.sc.sc) && max(a.sc.fs, a.sc.sc) == max(b.sc.fs, b.sc.sc)) { // this case can take more queries, but should happen very few cases // ask randomly untill t.fs == t.sc while(true) { int t = rand() % 3; vi POS = {a.fs.sc, a.fs.fs, b.fs.sc, b.fs.fs}; int i = POS[t], j = POS[t+1]; iiii k = get(i, j); int first = max(a.sc.fs, a.sc.sc); int second = min(a.sc.fs, a.sc.sc); if(k.sc.fs == k.sc.sc) { ANS[i] = k.sc.sc; ANS[j] = k.sc.sc; int oth = first; if(oth == k.sc.sc) oth = second; rep(l,0,4) { if(l != t && l != t+1) { ANS[POS[l]] = oth; } } return iiii(ii(-1,-1),ii(-1,-1)); // Finished } } } //// return new iiii iiii t = get(a.fs.fs, b.fs.fs); // maybe special case x y x y if(t.sc.fs == t.sc.sc) { // same value, fix ans ANS[a.fs.fs] = t.sc.fs; ANS[b.fs.fs] = t.sc.fs; int oth1 = max(a.sc.fs, a.sc.sc); if(t.sc.fs == oth1) oth1 = min(a.sc.sc, a.sc.fs); ANS[a.fs.sc] = oth1; int oth2 = max(b.sc.fs, b.sc.sc); if(t.sc.fs == oth2) oth2 = min(b.sc.sc, b.sc.fs); ANS[b.fs.sc] = oth2; return iiii(ii(-1,-1),ii(-1,-1)); // Finished } else { // fix ans and determine the two if(!share(a,b)) { // x y z w int oth1 = max(a.sc.fs, a.sc.sc); if(t.sc.fs == oth1 || t.sc.sc == oth1) oth1 = min(a.sc.fs, a.sc.sc); ANS[a.fs.sc] = oth1; int oth2 = max(b.sc.fs, b.sc.sc); if(t.sc.fs == oth2 || t.sc.sc == oth2) oth2 = min(b.sc.fs, b.sc.sc); ANS[b.fs.sc] = oth2; } else { // both wrong int shared_val = share(a,b); if(t.sc.fs != shared_val && t.sc.sc != shared_val) { ANS[a.fs.sc] = shared_val; ANS[b.fs.sc] = shared_val; } else { int oth1 = max(a.sc.fs, a.sc.sc); if(oth1 == shared_val) oth1 = min(a.sc.fs, a.sc.sc); int oth2 = max(b.sc.fs, b.sc.sc); if(oth2 == shared_val) oth2 = min(b.sc.fs, b.sc.sc); if(oth1 == t.sc.fs || oth1 == t.sc.sc) { ANS[a.fs.sc] = shared_val; ANS[b.fs.sc] = oth2; } else if(oth2 == t.sc.fs || oth2 == t.sc.sc) { ANS[a.fs.sc] = oth1; ANS[b.fs.sc] = shared_val; } else { assert(false && "line 170 gerist"); } } } return t; } } vi VIS; vvi E; vii MATCHING; void dfs(int at, int took_last) { if(VIS[at]) return; VIS[at] = 1; for(auto v : E[at]) { if(VIS[v]) continue; if(!took_last) { MATCHING.pb(ii(at,v)); } dfs(v, 1 - took_last); break; } } int main() { cin.sync_with_stdio(false); srand(time(NULL)); int mx = 0; int n = 100000; cin >> n; vector T; ANS = vi(n,0); vi P(n,0); rep(i,0,n) P[i] = i; random_shuffle(P.begin(), P.end()); for(int i = 0; i < n; i += 2) { iiii l = get(P[i], P[i+1]); if(l.sc.sc == l.sc.fs) { // same join(l, l); } else { T.pb(l); } } while(T.size() > 1) { vector NEW_T; vector> L; // pair guys together if someone left out then add to NEW_T map counts; // do maximum matching E = vvi(T.size(), vi()); VIS = vi(T.size(), 0); MATCHING.clear(); for(int k = 0; k < T.size(); k++) { counts[T[k].sc.fs].pb(k); counts[T[k].sc.sc].pb(k); } for(auto a : counts) { vi l = a.sc; if(l.size() == 2) { int pl1 = l[0], pl2 = l[1]; E[pl1].pb(pl2); E[pl2].pb(pl1); } } rep(i,0,T.size()) assert(E[i].size() <= 2); rep(i,0,T.size()) if(E[i].size() == 1 && !VIS[i]) dfs(i,0); rep(i,0,T.size()) if(E[i].size() == 2 && !VIS[i]) dfs(i,0); map OK; VIS = vi(n,0); for(auto a : MATCHING) { assert(a.fs != a.sc && "not same value"); VIS[a.fs] = 1; VIS[a.sc] = 1; L.pb(i8(T[a.fs], T[a.sc])); } vector NOT_USED; rep(i,0,T.size()) { if(!VIS[i]) NOT_USED.pb(T[i]); } if(NOT_USED.size() % 2 == 1) { NEW_T.pb(NOT_USED.back()); NOT_USED.pop_back(); } for(int i = 0; i < NOT_USED.size(); i += 2) { L.pb(i8(NOT_USED[i], NOT_USED[i+1])); } // run it for(int i = 0; i < L.size(); i++) { iiii ok = join(L[i].fs, L[i].sc); if(ok.sc.fs != -1) NEW_T.pb(ok); } T = NEW_T; } // find where they are located and join them, this will be a hard query if(T.size() == 1) { iiii last = T[0]; int val1 = last.sc.fs; int val2 = last.sc.sc; int index_1 = 0, index_2 = 0; rep(i,0,n) { if(ANS[i] == val1) index_1 = i; if(ANS[i] == val2) index_2 = i; } iiii ne = get(index_1, index_2); join(last, ne); } // write it out ans(ANS); mx = max(mx, quest); }