传送门

---

技不如人，肝败吓疯。

题解：

首先题目说交互库在相等的时候玄学返回值，这句话相当劝退。。。

但是冷静一下，其实返回的结果就是从$<$变成了$\le$，冷静下应该是能想到搞法的。

首先考虑task3，因为这个task有特殊性质而且限制小得吓人，显然有特殊做法。

此时的串显然是两段全0全1序列拼起来的，首先判断一下两边哪端是$0$哪端是$1$，然后二分，把$mid$和$mid+1$拿出来，询问$(\{mid,mid+1\},1)$，显然最靠前的$\{mid,mid+1\}>=1$就是$0,1$的分界线。

然后考虑怎么处理最大的task，注意到代价大概是在$5n$加上一点调整部分的花费。

任取三个还没有确定的位置$x,y,a$，询问$(\{x,y\},a)$和$(x,y)$，假设$x\le y$。

如果$x+y\le a$，那么可以确定$x=0$。 否则$x+y\ge a$，可以确定$y\ge a$，然后把$y$当成新的$a$继续做。

在这样的$y$换$a$的过程中，我们得到了一条单调的链，把这条链设成$x_1,x_2,\dots x_k$，但是可以发现最后会剩下一个不定位置$z$。

容易注意到$\max (x_k,z)=1$。然后对于原来那条链，直接用task3的做法二分，最后通过奇偶性判断出$z$的权值，发现代价大概是$5n+3\log n+o(1)$，是可以跑过的。

---

代码：

#include "shop.h" #include<bits/stdc++.h> #define ll long long #define re register #define cs const using std::cerr; cs int N=1e5+7; int tp1[2],tp2[2],q[N],ct,st[N],tp; inline int qy(int x,int y){ tp1[0]=x,tp2[0]=y; return query(tp1,1,tp2,1); } inline int qy(int x,int y,int z){ tp1[0]=x,tp1[1]=y,tp2[0]=z; return query(tp1,2,tp2,1); } inline int binary(int n,int k,int ans[]){ int l=0,r=n-2,res=n-1; while(l<=r){ int m=l+r>>1; if(!qy(q[m],q[m+1],q[n-1]))res=m,r=m-1; else l=m+1; } int tmp=res; if(((n-res)&1)^k)++res; for(int re i=0;i<res;++i)ans[q[i]]=0; for(int re i=res;i<n;++i)ans[q[i]]=1; return tmp; } void find_price(int task_id,int n,int k,int ans[]){ for(int re i=0;i<n;++i)ans[i]=0; if(task_id==3){ for(int re i=0;i<n;++i)q[i]=i; if(!qy(0,n-1))std::reverse(q,q+n); binary(n,k,ans);return ; } if(n==1){ans[0]=1;return ;} if(n==2){ int mx=qy(0,1)?1:0; ans[mx]=1;if(!k)ans[mx^1]=1; return ; } st[0]=ct=0,tp=1; for(int re i=1;i<n;++i)q[++ct]=i; while(ct>1){ if(qy(q[ct],q[ct-1],st[tp-1])){ if(!qy(q[ct],q[ct-1]))std::swap(q[ct],q[ct-1]); ans[q[ct]]=0; } else { if(qy(q[ct],q[ct-1]))std::swap(q[ct],q[ct-1]); st[tp++]=q[ct]; }--ct; } if(qy(q[ct],st[tp-1])){ ans[st[tp-1]]=1;int mx=q[ct];ct=0; for(int re i=0;i<tp;++i)q[ct++]=st[i]; int res=binary(ct,k,ans); k^=(ct-res-1)&1,res=q[res]; if(qy(res,mx,st[tp-1])){ if(!qy(res,mx))std::swap(res,mx); ans[res]=0; } else { if(qy(res,mx))std::swap(res,mx); ans[res]=1,k^=1; }ans[mx]=k; }else { ans[q[ct]]=1,st[tp++]=q[ct],ct=0; for(int re i=0;i<tp;++i)q[ct++]=st[i]; binary(ct,k,ans); } }