Link.
P.S.
半个上午和半个下午被这题折磨光光了/ll /ll /ll
本文共出现了 10 次 binary search /tuu
这个做法可能比较菜，最大的点用了 18729 个询问。
Description.
交互，有张 \(n(n\le 600)\) 的联通图，每次你给一个点集，交互库返回导出子图边数。
在 \(20000\) 次内判断图是否是二分图，如果是就输出一侧的所有点，否则就输出任意一个奇环。
Solution.
Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
这题基本从上到下有无数个 binary search。
挖一些询问方式
- \(\text{qry}(S\cup\{x\})-\text{qry}(S)\) 可以询问出 \(x\) 到 \(S\) 的边数。
- \(\text{qry}(S\cup T)-\text{qry}(S)-\text{qry}(T)\) 可以询问出 \(S\) 和 \(T\) 集合之间的边。
首先，我们考虑假设给了一条链怎么做。
找到一个起点，每次往两端扩展，总共需要扩展 \(O(n)\) 次。
每次相当于要从剩下的集合中找到一个和当前端点相邻的点集，并扩展。
这时我们就可以用 binary search 来解决这个问题了。
每次查寻前缀和当前端点有几条连边，具有单调性，可以 binary search。
总复杂度 \(O(n\log n)\)
注：这一段做法可能不够优秀，但是最后的能 AC 的做法是基于这个做法优化的
发现这个东西可以扩展，可以把 binary search 扩展成分治。
我们先把当前所有的没被扩展的点拿出来，排成一个序列。
我们每次询问，可以询问的是当前扩展的点集和序列中的若干点有无连边。
可以考虑分治，如果当前这段区间有就继续，否则就没有。
复杂度分析一下发现是 \(O(\min(n,cnt\times \log n))\) 的，和线段树的单点查询有点类似。
其中 \(cnt\) 表示的是和当前点集相邻的点数量。
每次找到和当前相邻的点集，判断内部有无连边，然后继续扩展。
发现均摊一下每个点只可能被扩展一次，总复杂度 \(O(n\log n)\)。
然后发现有一个重要问题没有考虑：怎么输出奇环。
可以考虑建出一个生成树，然后找到奇偶相同层之间的连边。
这个东西可以 binary search，就二分序列。
如果左边内部有边，就二分左边，否则如果右边有边，就二分右边。
否则必然是左右连的边，就 binary search 找到左边的和右边有边的点，然后 binary search 找到右边的和左边有连边的点。
然后这两个点肯定构成一个奇环，直接输出生成树上两点链就行了。
然后生成树怎么建：类似于 bfs 一样一层一层扩展。
每扩展到下一层，在分治边缘，需要把新点加到当前树中。
此时可以直接用 binary search 找到任意一个和当前这个点有连边的点。
然后让当前新扩展到的点的父亲是他就行了。
分析一下复杂度，找父亲每个点要找一遍 \(O(n\log n)\)。
分治总复杂度是 \(O(n\log n)\)，找奇环总复杂度是 \(O(\log n)\)。
总复杂度 \(O(n\log n)\)，在 \(600\) 下跑在 \(20000\) 以内应该很稳。
冲了一发
次数超了！！！观察上面代码的分治过程。
发现每次分治需要 \(2.5\) 的常数，每个点二分父亲时大概需要 \(2\) 的常数。
总询问次数上限是 \(4.5n\log n \approx 24917\)。
所以你被卡常了！！！本地测了一下，发现 \(600\) 的环大概需要 \(21530\) 次。
而且这个也没办法优化，常数巨大，瞬间爆毙。
考虑能不能从方法上优化这个东西，发现这个东西本质上就是在做 bfs。
如果我们每次枚举一个点作为父亲让他来扩展，这样就不需要在底层二分了，去掉了 \(2\) 的常数。
同时分治时也不需要查寻三次只需要查寻两次了，又减少了 \(1\) 的常数。
这样就能过了。
Coding.
稍微写了点注释
有一大堆调试信息的代码（有点精污，就不放在版面上了
//Coded by leapfrog on 2021.10.27 {{{
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=605;typedef vector<int>vi;int n,fa[N],dep[N];char vs[N];
inline int qry(vi q)
{//询问
int x=0;if((int)q.size()<2) return 0;
printf("? %d\n",(int)q.size());for(auto x:q) printf("%d ",x);
putchar('\n'),fflush(stdout);read(x);if(x==-1) exit(0);else return x;
}
inline vi split(const vi &a,int l,int r)
{//取一个 vector 的区间
vi rs;for(int i=l;i<=r;i++) rs.push_back(a[i]);
return rs;
}
inline vi merge(const vi &a,const vi &b)
{//合并两个 vector
vi r;if(a.size()>b.size()) {r=a;for(auto x:b) r.push_back(x);}
else {r=b;for(auto x:a) r.push_back(x);}
return r;
}
inline vi solve(const vi &x,int ls,int l,int r)
{//分治
int md=(l+r)>>1,vl;vi rs,tmp;
if(l==r) return rs.push_back(x[l]),dep[x[l]]=dep[fa[x[l]]=ls]+1,rs;
tmp=split(x,l,md),vl=qry(tmp),tmp.push_back(ls),vl=qry(tmp)-vl;
for(int i=l;i<=md;i++) vl-=vs[x[i]];
if(vl) rs=merge(rs,solve(x,ls,l,md));
tmp=split(x,md+1,r),vl=qry(tmp),tmp.push_back(ls),vl=qry(tmp)-vl;
for(int i=md+1;i<=r;i++) vl-=vs[x[i]];
if(vl) rs=merge(rs,solve(x,ls,md+1,r));
return rs;
}
inline int LCA(int x,int y)
{//暴跳求 LCA
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=fa[x];
while(x!=y) x=fa[x],y=fa[y];
return x;
}
inline void NOT(vi v)
{//输出奇环
int l=0,r=v.size()-1,md=(l+r)>>1;
for(;l<=r;md=(l+r)>>1)
{//第一次二分
if(qry(split(v,l,md))) r=md;
else if(qry(split(v,md+1,r))) l=md+1;
else break;
}int rsl=-1,rsr=-1;//后两次二分↓↓
for(int L=l,R=md,mid=(L+R)>>1;L<=R;mid=(L+R)>>1)
if(qry(merge(split(v,l,mid),split(v,md+1,r)))) rsl=mid,R=mid-1;else L=mid+1;
for(int L=md+1,R=r,mid=(L+R)>>1;L<=R;mid=(L+R)>>1)
if(qry(merge(split(v,rsl,rsl),split(v,L,mid)))) rsr=mid,R=mid-1;else L=mid+1;
int x=v[rsl],y=v[rsr],lc=LCA(x,y);printf("N %d\n",dep[x]+dep[y]-dep[lc]*2+1);
vector<int>tp;while(x!=lc) printf("%d ",x),x=fa[x];
printf("%d ",lc);while(y!=lc) tp.push_back(y),y=fa[y];
reverse(tp.begin(),tp.end());for(auto w:tp) printf("%d ",w);
putchar('\n'),fflush(stdout),exit(0);
}
int main()
{
queue<int>q;read(n),vs[1]=1,q.push(1);
while(!q.empty())
{//bfs
int x=q.front();q.pop();vi nw;
for(int i=1;i<=n;i++) if(!vs[i]) nw.push_back(i);
int qwq=qry(nw);nw.push_back(x),qwq=qry(nw)-qwq,nw.pop_back();if(!qwq) continue;
vi tp=solve(nw,x,0,nw.size()-1);for(auto x:tp) q.push(x),vs[x]=1;
}
vi tp;for(int i=1;i<=n;i++) if(dep[i]&1) tp.push_back(i);
if(qry(tp)) return NOT(tp),0;else tp.clear();
for(int i=1;i<=n;i++) if(!(dep[i]&1)) tp.push_back(i);
if(qry(tp)) return NOT(tp),0;else printf("Y %d\n",(int)tp.size());
for(auto x:tp) printf("%d ",x);
return putchar('\n'),fflush(stdout),0;
}