交互题。
评测机会在 \([1,10^{18}]\) 中随机选择一个整数 \(x\)，你需要在不超过 \(q\) 次询问内猜出 \(x\)。
每次你可以询问一个整数 \(y\)，询问 \(y\) 与 \(x\) 的大小关系。
特别的，评测机会有 \(p \%\) 的概率会出错。
| 子任务编号 | 子任务分值 | \(p=\) | \(q=\) | 时间限制 |
|---|---|---|---|---|
| \(1\) | \(5\) | \(0\) | \(60\) | \(\texttt{1s}\) |
| \(2\) | \(10\) | \(10\) | \(500\) | \(\texttt{1s}\) |
| \(3\) | \(10\) | \(25\) | \(2000\) | \(\texttt{1s}\) |
| \(4\) | \(15\) | \(25\) | \(1000\) | \(\texttt{1s}\) |
| \(5\) | \(20\) | \(25\) | \(700\) | \(\texttt{1s}\) |
| \(6\) | \(10\) | \(25\) | \(400\) | \(\texttt{1s}\) |
| \(7\) | \(10\) | \(40\) | \(2500\) | \(\texttt{1s}\) |
| \(8\) | \(10\) | \(45\) | \(10000\) | \(\texttt{1s}\) |
| \(9\) | \(5\) | \(48\) | \(62500\) | \(\texttt{3s}\) |
| \(10\) | \(5\) | \(49\) | \(250000\) | \(\texttt{10s}\) |
令 \(P = p \%\)。
我们不妨令答案为 \(i\) 的概率为 \(p_i\)，则初始时 \(p_i = \dfrac{1}{10^{18}}\)。
考虑当前询问对 \(p_i\) 造成的影响。
首先，对于 \(y = x\) 的询问，我们此时已经知道答案了，可以直接返回。
\(y < x\) 和 \(y > x\) 是对称的，接下来考虑评测机回答 \(y < x\) 的情况。
此时，有 \(1-P\) 的概率满足 \(y < x\)，有 \(P\) 的概率满足 \(y > x\)，直接乘上概率即可。
但是，直接维护 \(p_i\) 很不方便，考虑维护 \(q_i\) 使得 \(q_i\) 与 \(p_i\) 成比例，则可以看成：
-
对于 \(i < y\)，\(q_i \leftarrow P \times q_i\)。
-
对于 \(i = y\)，\(q_i \leftarrow 0\)。
-
对于 \(i > y\)，\(q_i \leftarrow (1-P) \times q_i\)。
初始时令 \(q_i = 1\) 即可。
然而我们发现，这样做会有很大的精度误差，考虑整体除以 \(1-P\)，则过程等价于：
-
对于 \(i < y\)，\(q_i \leftarrow \dfrac{P}{1-P} \times q_i\)。
-
对于 \(i = y\)，\(q_i \leftarrow 0\)。
最后回答 \(q_i\) 最大的 \(i\) 即可，接下来考虑如何选取询问的 \(y\)。
容易想到每次询问的 \(y\) 要使左右两边的 \(q_i\) 之和尽量接近。
这样的话，无论回答 \(<\) 和 \(>\) 都能保持较为平均的情况。
考虑这个做法的正确性，直观感受上他很对，事实上他也很对，证明不会。
你发现最后没有必要找 \(q\) 最大的位置，直接按照上面的过程一个一个问即可。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define double long double
long long n;
int tot=1;
struct Node{long long l,r,lc,rc;double sum,maxn,tag;
}a[10000010];
void build(int id,long long l,long long r){a[id].l=l;a[id].r=r;a[id].sum=r-l+1;a[id].maxn=1;a[id].tag=1;
}
void pushdown(int id){long long mid=(a[id].l+a[id].r)/2;if(!a[id].lc){a[id].lc=++tot;build(a[id].lc,a[id].l,mid);}if(!a[id].rc){a[id].rc=++tot;build(a[id].rc,mid+1,a[id].r);}a[a[id].lc].sum*=a[id].tag;a[a[id].lc].maxn*=a[id].tag;a[a[id].lc].tag*=a[id].tag;a[a[id].rc].sum*=a[id].tag;a[a[id].rc].maxn*=a[id].tag;a[a[id].rc].tag*=a[id].tag;a[id].tag=1;
}
void pushup(int id){a[id].sum=a[a[id].lc].sum+a[a[id].rc].sum;a[id].maxn=max(a[a[id].lc].maxn,a[a[id].rc].maxn);
}
long long query(int id,double num){if(a[id].l==a[id].r){return a[id].l;}pushdown(id);if(a[a[id].lc].sum>=num){return query(a[id].lc,num);}else{return query(a[id].rc,num-a[a[id].lc].sum);}
}
void modify(int id,long long l,long long r,double num){if(l<=a[id].l && a[id].r<=r){a[id].sum*=num;a[id].maxn*=num;a[id].tag*=num;return ;}pushdown(id);if(l<=a[a[id].lc].r){modify(a[id].lc,l,r,num);}if(a[a[id].rc].l<=r){modify(a[id].rc,l,r,num);}pushup(id);
}
int main(){int p,q;cin>>n>>p>>q;double k=p/(100.0-p);build(1,1,n);while(q--){long long y=query(1,a[1].sum/2.0);cout<<y<<endl;char ch;cin>>ch;if(ch=='<'){if(y>1){modify(1,1,y-1,k);}modify(1,y,y,0);}else if(ch=='>'){if(y<n){modify(1,y+1,n,k);}modify(1,y,y,0);}else{break;}}return 0;
}
交了几发，平均下来只会错一个点，正确率还行。