// This starts generating n/2 pairs. // It then queries pairs of pairs while shuffling (to avoid queries of type {x, y}, {x, y}). // It should take fewer than (not much fewer though) n - 1 moves to solve all but one pair. #include #include #include #include #define MAXN 100000 #define rep(E, F) for (E = 0; E < (F); E++) int min(int a, int b) { if (a > b) return b; return a; } int max(int a, int b) { if (a < b) return b; return a; } int get_int() { int r = 0, c = getchar(), s = 1; while (c != '-' && c < '0' || c > '9') c = getchar(); while (c == '-') s *= -1, c = getchar(); while (c >= '0' && c <= '9') r = r*10 + c - '0', c = getchar(); return s*r; } void swap(int* a, int* b) { int s = *a; *a = *b; *b = s; } void shuffle(int* a, int n) { for (int i = 0, j; i < n; i++) { j = rand()%(n - i); swap(&a[j], &a[n - 1 - i]); } } typedef struct par{ int x, y, z, w;} par; void par_swap(par* a, par* b) { par s = *a; *a = *b; *b = s; } par topar(int x, int y, int z, int w) { par r = {x, y, z, w}; return r; } int cmp(const void *p1, const void *p2) { return ((par*)p1)->x - ((par*)p2)->x; } void par_shuffle(par* a, int n) { for (int i = 0, j; i < n; i++) { j = rand()%(n - i); par_swap(&a[j], &a[n - 1 - i]); } } par a[MAXN][2]; int n, ss[2], b[MAXN], p[MAXN], st = 0, aa[MAXN]; par s[2][MAXN]; void query(int x, int y, int *xx, int *yy) { printf("? %d %d\n", x + 1, y + 1); fflush(stdout); *xx = get_int(), *yy = get_int(); } void fix(int i, int x) { b[i] = x; } int par_eq(par a, par b) { if (min(a.x, a.y) != min(b.x, b.y)) return 0; if (max(a.x, a.y) != max(b.x, b.y)) return 0; if (min(a.z, a.w) != min(b.z, b.w)) return 0; if (max(a.z, a.w) != max(b.z, b.w)) return 0; return 1; } void rem(par *a, par p) { // removes p from a. a only has two elements. if (par_eq(a[0], p)) par_swap(&a[0], &a[1]); } int t1, t2, t3, t4; void step1(par p1, par p2) { int x, y; if (p1.x == p2.y || p1.y == p2.x) swap(&p2.x, &p2.y); rem(a[p1.x], p1), aa[p1.x]--; rem(a[p1.y], p1), aa[p1.y]--; rem(a[p2.x], p2), aa[p2.x]--; rem(a[p2.y], p2), aa[p2.y]--; if (p1.x == p2.x && p1.y == p2.y) { s[st][ss[1 - st]++] = p1, s[st][ss[1 - st]++] = p2; return; // risky aa[p1.x] = aa[p1.y] = 0; while (1) { t1++; query(p1.z, p2.z, &x, &y); if (x == y) { fix(p1.z, x); fix(p2.z, x); fix(p1.w, p1.x + p1.y - x); fix(p2.w, p1.x + p1.y - x); break; } t1++; query(p1.z, p1.w, &x, &y); if (x == y) { fix(p1.z, x); fix(p1.w, x); fix(p2.z, p1.x + p1.y - x); fix(p2.w, p1.x + p1.y - x); break; } } return; } if (p1.x == p2.y) swap(&p2.x, &p2.y); if (p1.y == p2.x) swap(&p1.x, &p1.y); if (p1.y == p2.y) swap(&p1.x, &p1.y), swap(&p2.x, &p2.y); if (p1.x == p2.x) { t2++; query(p1.z, p2.z, &x, &y); if (x == y) { fix(p1.z, x); fix(p2.z, x); fix(p1.w, p1.x + p1.y - x); fix(p2.w, p2.x + p2.y - x); } else { if (x == p2.y || y == p1.y) swap(&x, &y); fix(p1.w, p1.x + p1.y - x); fix(p2.w, p2.x + p2.y - y); s[1 - st][ss[1 - st]++] = topar(x, y, p1.z, p2.z); } return; } t3++; query(p1.z, p2.z, &x, &y); if (x != p1.x && x != p1.y) swap(&x, &y); fix(p1.w, p1.x + p1.y - x); fix(p2.w, p2.x + p2.y - y); s[1 - st][ss[1 - st]++] = topar(x, y, p1.z, p2.z); return; } void step3(par p) { int i, x, y; rep(i, n) if (b[i] == p.x && i != p.z && i != p.w) break; while (1) { t4++; query(i, p.z, &x, &y); if (x == y) { fix(p.z, x); fix(p.w, p.x + p.y - x); break; } t4++; query(p.w, p.z, &x, &y); if (x == y) { fix(p.z, x); fix(p.w, x); fix(i, p.x + p.y - x); break; } } } int main() { srand(10); int i, x, y; n = get_int(); rep(i, n) aa[i] = 0; rep(i, n) p[i] = i; shuffle(p, n); st = ss[0] = 0; rep(i, n/2) { query(p[i*2], p[2*i + 1], &x, &y); if (x == y) fix(p[2*i], x), fix(p[2*i + 1], y); else s[st][ss[st]++] = topar(x, y, p[2*i], p[2*i + 1]); } t1 = t2 = t3 = t4 = 0; while (1) { ss[1 - st] = 0; par_shuffle(s[st], ss[st]); while (ss[st] > 1) { par p1 = s[st][--ss[st]], p2 = s[st][--ss[st]]; step1(p1, p2); } if (ss[st] == 1) s[1 - st][ss[1 - st]++] = s[st][--ss[st]]; st = 1 - st; if (ss[st] < 2) break; } if (ss[st] != 0) step3(s[st][0]); printf("!"); rep(i, n) printf(" %d", b[i]); printf("\n"); fprintf(stderr, "ts: %d %d %d %d\n", t1, t2, t3, t4); return 0; }