交互题
一个 01 序列，告诉你其中 1 有奇数个还是偶数个，每次可以给定两个集合 $A$,$B$，系统会告诉你 $A \leq B$ 或者 $B \leq A$
求序列
交互次数要求 $5n + O(log_2 n)$
有一个 subtask 满足原序列是一条从不上升或者不下降的链，要求 $O(log_2n)$
sol：
首先有一个交互次数 $2n + 5n$ 的做法：首先 $2n$ 次找出最大值，最大的那个肯定是 $1$，之后每次问两个还不确定的（$a,b$），$a+b$ 是否大于等于 $1$
如果大于等于，那么 $a,b$ 中较大的是 $1$，否则 $a,b$ 中较小的是 $0$。最后特判一下奇偶性不符的情况即可
然后对于一条链的情况，首先，两个端点一定有一个 1，二分找出一个位置最小的 $x$ 使得 $p[x] + p[x+1] \geq 1$ 即可
分界线那里用奇偶性特判一下 $O(log_2n)$
正解
发现 5n 的部分不太好优化，考虑一边 5n 一边确定一个递增的关系，然后用 logn 次确定那条链
具体地，可以从三个数 $(x,y,z)$ 开始，先比较 $x,y$，不妨设大的那个是 $y$
如果 $x+y \leq z$，则 $x=0$，再找一个 $x$
否则 $y \geq z$，把 $y$ 放到 $z$ 的位置，再找一个 $y$
这样会确定若干个 $0$ ，剩一个比不出去的，和一条递增的链
容易知道比不出去的和链最大值中较大的那个是 $1$，可以直接上二分
二分之后还有一个不确定的分界线和一个比不出去的，$O(1)$ 讨论一下即可
#include <bits/stdc++.h> #include "shop.h" #define LL long long #define rep(i, s, t) for (register int i = s, i##end = t; i <= i##end; ++i) #define dwn(i, s, t) for (register int i = s, i##end = t; i >= i##end; --i) using namespace std; int arr[5], brr[5]; int ans[100010], que[100010], chain[100010]; int ask(int x, int y) { arr[0] = x, brr[0] = y; return query(arr, 1, brr, 1); } int ask2(int x, int fst, int scd) { arr[0] = x, brr[0] = fst, brr[1] = scd; return query(arr, 1, brr, 2); } void find_price(int task_id, int N, int K, int ans[]) { auto solvechain = [&](int N, int K) { int l = 0, r = N - 2, res = N - 1; while (l <= r) { int mid = (l + r) >> 1; if (ask2(que[N - 1], que[mid], que[mid + 1])) res = mid, r = mid - 1; else l = mid + 1; } int val = res; if (K != ((N - res) & 1)) res++; rep(i, 0, res - 1) ans[que[i]] = 0; rep(i, res, N - 1) ans[que[i]] = 1; return val; }; for (int i = 0; i < N; ++i) ans[i] = 0; if (task_id == 3) { for (int i = 0; i < N; ++i) que[i] = i; if (ask(N - 1, 0)) reverse(que, que + N); solvechain(N, K); } else if (task_id == 6) { if (N == 1) ans[0] = 1; else if (N == 2) { int mx = ask(0, 1) ? 1 : 0; ans[mx] = 1; if (!K) ans[!mx] = 1; } else { int dfn = N - 1, cd = 1; chain[0] = 0; for (int i = 1; i < N; ++i) que[i] = i; while (dfn > 1) { if (!ask2(chain[cd - 1], que[dfn], que[dfn - 1])) { if (!ask(que[dfn], que[dfn - 1])) swap(que[dfn], que[dfn - 1]); ans[que[dfn]] = 0; } else { if (ask(que[dfn], que[dfn - 1])) swap(que[dfn], que[dfn - 1]); chain[cd++] = que[dfn]; } dfn--; } if (ask(que[dfn], chain[cd - 1])) { ans[chain[cd - 1]] = 1; int cmx = que[dfn]; dfn = cd; for (int i = 0; i < cd; ++i) que[i] = chain[i]; int cur = solvechain(dfn, K); K ^= ((dfn - cur - 1) & 1); cur = que[cur]; if (!ask2(chain[cd - 1], cmx, cur)) { if (ask(cmx, cur)) ans[cmx] = 0; else ans[cur] = 0; } else { if (ask(cur, cmx)) ans[cmx] = 1; else ans[cur] = 1; K ^= 1; } ans[cmx] = K; } else { ans[que[dfn]] = 1; chain[cd++] = que[dfn]; for (int i = 0; i < cd; ++i) que[i] = chain[i]; solvechain(cd, K); } } } else { int mx = 0; for (int i = 1; i < N; ++i) if (ask(mx, i) == 1) mx = i; ans[mx] = 1; int dfn = 0; K ^= 1; for (int i = 0; i < N; ++i) { if (i == mx) continue; que[++dfn] = i; } while (dfn > 1) { if (ask2(mx, que[dfn], que[dfn - 1]) == 0) { if (ask(que[dfn - 1], que[dfn])) swap(que[dfn - 1], que[dfn]); ans[que[dfn]] = 0; } else { if (!ask(que[dfn - 1], que[dfn])) swap(que[dfn - 1], que[dfn]); ans[que[dfn]] = 1; K ^= 1; } dfn--; } if (K && dfn) ans[que[dfn]] = 1; } }