题目
交互题；
有\(n\)个物品，每个物品的价格为０或者１;
给出为１的物品的个数奇偶性ｋ，并保证至少有一个价格为１；
每次可以询问一个集合S的另一个集合T的价值和的大小，交互库会返回>=或者<=;
一次交互的代价为|S|+|T|，总阈值为Ｍ；
问每个物品的价值；
\(n \le 10^5 \ , \ M = 500100 \ , \ K=0/1\);
题解
利用\(2N\)次找出最大的数，即１
接下来对于\(x \le y\)，如果\(x+y\le 1\) ，则\(x=0\),否则\(y=1\)
复杂度：\(O(7N)\) ;
随便找一个\(z\)，比较\(x+y\)和\(z\)：
若\(x+y \le z\) , 则\(x = 0\)若\(x+y \ge z\)，则\(y \ge z\)，用\(y\)去替代\(z\)
最后会的到很多0和一条单调递增的链，同时最后\(max(x,z) = 1\)，得到一个１；
根据sub3的做法在链上二分，利用奇偶性判断\(mid\)位置的答案；
复杂度：\(O(5N+ 3log \ N)\) ;
#include "shop.h"#include
using namespace std;const int N=100010;int st[N],top,q1[N],t1,q2[N],t2;bool cmp1(int a,int b){ q1[0]=a,q2[0]=b; return query(q1,1,q2,1);}bool cmp2(int a,int b,int c){ q1[0]=a,q1[1]=b;q2[0]=c; return query(q1,2,q2,1);}void swp(int&a,int&b){if(!cmp1(a,b))swap(a,b);}void find_price(int id,int n,int k,int ans[]){ top=0; if(n==1){ans[0]=k;return;} if(n==2){ int x=0,y=1;swp(x,y); if(k)ans[y]=1,ans[x]=0; else ans[x]=ans[y]=1; return ; } if(id==3){ if(!cmp1(0,n-1)){ int l=1,r=n-1; while(l