#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; } 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; } par a[MAXN][2]; int n, ss, b[MAXN], s[MAXN], aa[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) { 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); par pp = topar(x, y, p1.z, p2.z); a[x][aa[x]++] = pp, a[y][aa[y]++] = pp; } if (aa[p1.x] == 1) s[ss++] = p1.x; if (aa[p1.y] == 1) s[ss++] = p1.y; if (aa[p2.x] == 1) s[ss++] = p2.x; if (aa[p2.y] == 1) s[ss++] = p2.y; // new orphans. these might be fixed later incidentally. return; } return; } par h[MAXN]; int hh = 0; void step2(par p1, par p2) { int x, y; 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); h[hh++] = 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() { int i, x, y; n = get_int(); rep(i, n) aa[i] = 0; rep(i, n/2) { query(i*2, 2*i + 1, &x, &y); if (x == y) fix(2*i, x), fix(2*i + 1, y); else { par pp = topar(x, y, 2*i, 2*i + 1); a[x][aa[x]++] = pp, a[y][aa[y]++] = pp; } } t1 = t2 = t3 = t4 = 0; rep(i, n) { if (aa[i] == 0) continue; step1(a[i][0], a[i][1]); while (ss > 0) { x = s[--ss]; if (aa[x] == 0) continue; // already been deorphaned. y = a[x][0].x + a[x][0].y - x; if (aa[y] == 1) { h[hh++] = a[x][0]; aa[x] = aa[y] = 0; } else if (par_eq(a[x][0], a[y][0])) step1(a[x][0], a[y][1]); else if (par_eq(a[x][0], a[y][1])) step1(a[x][0], a[y][0]); else assert(0); } } while (hh > 1) { par p1 = h[--hh], p2 = h[--hh]; step2(p1, p2); } if (hh != 0) step3(h[0]); printf("!"); rep(i, n) printf(" %d", b[i]); printf("\n"); fprintf(stderr, "%d %d %d %d\n", t1, t2, t3, t4); return 0; } /* We start by doing $n/2$ queries of the form "2*i 2*i + 1". This will give us $n/2$ tuples $(x, y, i, j)$ indicating that either the $i$th card is $x$ and the $j$th card $y$, or the $j$th card is $x$ and the $i$th card $y$. We can ignore tuples of the form $(x, x, i, j)$. We then want to take two tuples and simplify them by performing queries. For a pair of tuples we have three types: Type 1: The tuples are of the form $(x, y, i, j)$ and $(x, y, a, b)$. Type 2: The tuples are of the form $(x, y, i, j)$ and $(y, z, a, b)$, with $x \neq z$. Type 3: The tuples are of the form $(x, y, i, j)$ and $(z, w, a, b)$, with $x$, $y$, $z$, and $w$ all being distinct. Consider, for example, Type 3. If we query "i a" and get cards $y$ and $z$, then we know that the $j$th card is $x$ and the $b$th card is $w$. We can similar results if we get other cards then $y$ and $z$. So we can always reduce a Type 3 pair of tuples to a single tuples using one query. Consider next a pair of Type 1. If we query "i a" and get card $x$ and $y$ then we can't know which pair the $x$ came from which the $y$ came from. However, if we get cards $x$ and $x$ or $y$ and $y$ then we know the location of all four cards. These two scenarios have equal chances of happening. By alternating between queries "i a" and "i i" we have process that finds the location of all four cards in the tuples in $k$ moves with probability $2^{-k}$ (and the expected number of queries is $2$). Finally consider a pair of Type 2. If we query "i a" and get cards $x$ and $z$, $y$ and $z$, or $x$ and $y$ we are in the same situation as in Type 3. But if we get cards $y$ and $y$, then we know the location of all 4 cards in the pair of tuples. These four scenarios have equal chances of happening. So we have a $25\%$ chance of find all the cards and $75\%$ of finding two of four cards. That makes this type of pair better then the others. So we want to maximise the number of pairs of Type 2. The idea behind bergur-better.c: Consider the graph where the numbers from $1$ to $n/2$ are the nodes and there are edges between two nodes $x$ and $y$ if there is a tuple whose first two elements are $x$ and $y$. Note that in this graph the nodes have a degree of at most $2$ and if a node has degree $0$ than we know the location of both those cards. This graph is then a collection of disjoint cycles and paths (if we ignore the isolated nodes). A pair of Type 2 in this graph is represented by a node of degree $2$ (the edges from the node represent the pair of tuples). Let's say we have a long path and we decide to resolve a Type 2 pair of tuples at the start of it. Then we have a graph that looks like x y z O---O---O---O---O---O-... We then get one of the following graphs after resolving the first three nodes x y z 1. O O O---O---O---O-... x y z 2. O---O O---O---O---O-... x y z 3. O O---O---O---O---O-... y x z 4. O O---O---O---O---O-... So in three of four cases we get a slightly shorter path and in one case we get a slightly shorter path with an isolated tuple. If we had a cycle instead of a path then we could resolve any pair of Type 2 in it and that would resolve in a similar manner to a path, so we only need to consider the paths. We can then continue this process on our path until it has reduced to only isolated pairs (and maybe a pair of Type 1). Doing this to all the cycles in our graph (initially the graph contains only cycles) should give us a lot of queries of Type 2. Afterwards we are left with some queries, none of which are pairwise of Type 2. We can either handle them in no particular order which will give us a mix of Type 1 and Type 3 pairs. We could also try to minimise the number of Type 1 we need to handle. Both have the same expected number of queries needed to solve it, but the latter will gives us a more consistent number of queries. My submissions does the former. This process may leave you with one tuple leftover, let's call it $(x, y, i, j)$. You can then find the $x$ you already know the location of and solve this similar to a Type 1 pair of tuples. */