传送门
搬题解QwQ
首先最大值一定为 (1)，直接扫一遍两两比较 (O(2N)) 求出最大值
设最大值位置为 (a)，对于任意两个没有确定的位置 (x,y)
询问 ([a,x+y])，如果 (ale 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) 的代价确定 (xle y) 或者 (yge x)
假设 (xle y)
如果 (x+yle a)，那么 (x=0)
否则 (yge a)，把 (y) 当成新的 (a) 继续做
最后可以得到一个不确定的位置 (z) 和一条递增的链 (x_1...x_k)，其它的都是 (0)
(max(z,x_k)) 一定为 (1)，那么可以直接用 (Task3) 的方法二分
最后利用常数的代价 (+) 奇偶性求出 (z) 和二分中不确定的位置
# include "shop.h"
# include <bits/stdc++.h>
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);
}
}
}