#include #include #include #include #include #include using namespace std; // Edge between two values. struct Edge { // i,j: positions // a,b: values int i, a; int j, b; bool same() const { return a == b; } bool operator==(const Edge&) const = default; }; int n; vector> g; // The current values. vector vals; // List of vertices with degree 1 and 2 resp. set leaves; set middles; // Edges between two vertices of degree 1. vector leftovers; void inc_degree(int a) { if(g[a].empty()) { leaves.insert(a); } else if(g[a].size() == 1) { leaves.erase(a); middles.insert(a); } else { assert(false); } } // i, j: 0-based positions // a, b: 0-based values Edge query(int i, int j, bool silent = false) { cout << "? " << i + 1 << ' ' << j + 1 << endl; int a, b; cin >> a >> b; --a, --b; vals[i] = a; vals[j] = b; if(a != b and not silent) { inc_degree(a); inc_degree(b); g[a].push_back({i, a, j, b}); g[b].push_back({j, b, i, a}); } return {i, a, j, b}; } optional resolve(Edge e1, Edge e2) { if(e1.b == e2.a) swap(e1.a, e1.b), swap(e1.i, e1.j); if(e1.a == e2.a and e1.b == e2.b) { // abab auto a = e1.a, b = e1.b; auto e = query(e1.i, e2.i, true); if(e.same()) { vals[e1.j] = a + b - e.a; vals[e2.j] = a + b - e.a; return {}; } else { vals[e1.j] = a; vals[e2.j] = b; return resolve(e, {e1.j, a, e2.j, b}); } } // Try to make abac if(e1.a == e2.b or e1.b == e2.b) swap(e2.a, e2.b), swap(e2.i, e2.j); if(e1.b == e2.a) swap(e1.a, e1.b), swap(e1.i, e1.j); // abad or abcd auto a = e1.a, b = e1.b, c = e2.a, d = e2.b; auto e = query(e1.i, e2.i); vals[e1.j] = (e.a == b or e.b == b) ? a : b; vals[e2.j] = (e.a == d or e.b == d) ? c : d; if(e.same()) return {}; return e; } void remove_edge(Edge e) { for(int i = 0; i < 2; ++i) { for(auto x : {e.a, e.b}) { auto& ge = g[x]; if(auto it = find(ge.begin(), ge.end(), e); it != ge.end()) { ge.erase(it); } } swap(e.i, e.j), swap(e.a, e.b); } for(auto x : {e.a, e.b}) { leaves.erase(x); middles.erase(x); if(g[x].size() == 1) { leaves.insert(x); } else if(g[x].size() == 2) { middles.insert(x); } } } void try_middle(int a) { assert(g[a].size() == 2); auto e1 = g[a][0]; auto e2 = g[a][1]; g[a].clear(); middles.erase(a); assert(e1.a == a); assert(e2.a == a); remove_edge(e1); remove_edge(e2); resolve(e1, e2); } int main() { cin >> n; g.resize(n / 2); vals.resize(n); for(int i = 0; i < n; i += 2) { auto e = query(i, i + 1); if(e.same()) continue; auto [i_, a, j, b] = e; assert(i == i_); } for(int a = 0; a < n / 2; ++a) { if(g[a].size() == 1) leaves.insert(a); if(g[a].size() == 2) middles.insert(a); } while(!leaves.empty() or !middles.empty()) { if(!leaves.empty()) { auto a = *leaves.begin(); leaves.erase(a); assert(g[a].size() == 1); auto e1 = g[a][0]; auto [i, a_, j, b] = e1; assert(a_ == a); g[a].pop_back(); assert(!g[b].empty()); if(g[b].size() == 1) { // This is a lonely edge. leftovers.push_back(e1); g[b].clear(); leaves.erase(b); } else try_middle(b); } else { try_middle(*middles.begin()); } } while(leftovers.size() >= 2) { auto e1 = leftovers.back(); leftovers.pop_back(); auto e2 = leftovers.back(); leftovers.pop_back(); remove_edge(e1); remove_edge(e2); auto e = resolve(e1, e2); if(e) leftovers.push_back(*e); } // Resolve the final edge. if(not leftovers.empty()) { auto e1 = leftovers.back(); leftovers.pop_back(); // Find positions of e1.a, e2.b. auto e2 = e1; for(int i = 0; i < n; ++i) { if(vals[i] == e1.a and i != e1.i) e2.i = i; if(vals[i] == e1.b and i != e1.j) e2.j = i; } assert(resolve(e1, e2) == nullopt); } cout << "!"; for(auto x : vals) cout << ' ' << x + 1; cout << endl; }