搬题解QwQ 首先最大值一定为
\(1\)，直接扫一遍两两比较
\(O(2N)\) 求出最大值
设最大值位置为
\(a\)，对于任意两个没有确定的位置
\(x,y\) 询问
\([a,x+y]\)，如果
\(a\le x+y\) 那么
\(x,y\) 的最大值为
\(1\)，否则
\(x,y\) 最小值为
\(0\) 再询问
\([x,y]\) 即可
复杂度
\(O(7N)\) 考虑
\(Task3\)，首先花费
\(2\) 的代价找到端点的
\(1\) 假设序列为
\(00000....11111\)，只需要找到最靠前的位置
\(x\)，使得
\(x+(x+1)\ge 1\)，二分即可
然后
\(\ge x+1\) 的位置都是
\(1\)，
\(< x\) 的位置都是
\(0\)，利用奇偶性判断
\(x\) 是否为
\(1\) 再考虑
\(Task6\)，猜想复杂度为
\(5N+3logN\) 左右
任取三个没有确定的位置
\(x,y,a\)，询问
\([x+y,a]\)，再花费
\(2\) 的代价确定
\(x\le y\) 或者
\(y\ge x\) 假设
\(x\le y\) 如果
\(x+y\le a\)，那么
\(x=0\) 否则
\(y\ge a\)，把
\(y\) 当成新的
\(a\) 继续做
最后可以得到一个不确定的位置
\(z\) 和一条递增的链
\(x_1...x_k\)，其它的都是
\(0\)\(max(z,x_k)\) 一定为
\(1\)，那么可以直接用
\(Task3\) 的方法二分
最后利用常数的代价
\(+\) 奇偶性求出
\(z\) 和二分中不确定的位置
# include "shop.h"# include using namespace std;typedef long long ll;const int maxn(1e5 + 5);int tmp1[2], tmp2[2], que[maxn], cnt, st[maxn], tp;inline int Query1(int x, int y) { tmp1[0] = x, tmp2[0] = y; return query(tmp1, 1, tmp2, 1);}inline int Query2(int x, int y, int z) { tmp1[0] = x, tmp1[1] = y, tmp2[0] = z; return query(tmp1, 2, tmp2, 1);}inline int Binary(int n, int k, int *ans) { int i, l, r, mid, ret, v; l = 0, ret = n - 1, r = n - 2; while (l <= r) { mid = (l + r) >> 1; if (!Query2(que[mid], que[mid + 1], que[n - 1])) ret = mid, r = mid - 1; else l = mid + 1; } v = ret; if (((n - ret) & 1) ^ k) ++ret; for (i = 0; i < ret; ++i) ans[que[i]] = 0; for (i = ret; i < n; ++i) ans[que[i]] = 1; return v;}void find_price(int task_id, int n, int k, int ans[]) { int i, mx = 0, ret; for (i = 0; i < n; ++i) ans[i] = 0; if (task_id == 3) { for (i = 0; i < n; ++i) que[i] = i; if (!Query1(0, n - 1)) reverse(que, que + n); Binary(n, k, ans); }/* times = 7N else { for (i = 1; i < n; ++i) if (Query1(mx, i)) mx = i; ans[mx] = 1, cnt = 0, k ^= 1; for (i = 0; i < n; ++i) if (i ^ mx) que[++cnt] = i; while (cnt > 1) { if (Query2(que[cnt], que[cnt - 1], mx)) { if (!Query1(que[cnt], que[cnt - 1])) swap(que[cnt], que[cnt - 1]); ans[que[cnt]] = 0; } else { if (Query1(que[cnt], que[cnt - 1])) swap(que[cnt], que[cnt - 1]); ans[que[cnt]] = 1, k ^= 1; } --cnt; } if (k && cnt) ans[que[1]] = 1; }*/ else { if (n == 1) { ans[0] = 1; return; } if (n == 2) { mx = Query1(0, 1) ? 1 : 0; ans[mx] = 1; if (!k) ans[mx ^ 1] = 1; return; } st[0] = cnt = 0, tp = 1; for (i = 1; i < n; ++i) que[++cnt] = i; while (cnt > 1) { if (Query2(que[cnt], que[cnt - 1], st[tp - 1])) { if (!Query1(que[cnt], que[cnt - 1])) swap(que[cnt], que[cnt - 1]); ans[que[cnt]] = 0; } else { if (Query1(que[cnt], que[cnt - 1])) swap(que[cnt], que[cnt - 1]); st[tp++] = que[cnt]; } --cnt; } if (Query1(que[cnt], st[tp - 1])) { ans[st[tp - 1]] = 1, mx = que[cnt], cnt = 0; for (i = 0; i < tp; ++i) que[cnt++] = st[i]; ret = Binary(cnt, k, ans); k ^= (cnt - ret - 1) & 1, ret = que[ret]; if (Query2(ret, mx, st[tp - 1])) { if (!Query1(ret, mx)) swap(ret, mx); ans[ret] = 0; } else { if (Query1(ret, mx)) swap(ret, mx); ans[ret] = 1, k ^= 1; } ans[mx] = k; } else { ans[que[cnt]] = 1, st[tp++] = que[cnt], cnt = 0; for (i = 0; i < tp; ++i) que[cnt++] = st[i]; Binary(cnt, k, ans); } }}