RT,大概思路是先 bfs 出一棵生成树,然后判断,不是二分图再二分出同色有边的两个点。码风清新,思路清晰,现在是 WA,球球大家了!/bx
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int N=605;
#define vi vector<int>
#define pb push_back
vi all,q1,q2,qry,G[N],wa;
int n,m,col[N],vis[N];
inline void getall(){
all.clear();
for(int i=1;i<=n;i++)
if(!vis[i])all.pb(i);
}
queue<int>Q;
inline int query(){
if(qry.size()<=1)return 0;
printf("? %d\n",qry.size());
for(auto x:qry)
printf("%d ",x);puts("");
fflush(stdout);
int S=read();return S;
}
inline int Query(){
int S=0,S1=0,S2=0;
qry.clear();
for(auto x:q1)qry.pb(x);
S1=query();
qry.clear();
for(auto x:q2)qry.pb(x);
S2=query();
for(auto x:q1)qry.pb(x);
S=query();
return S-S1-S2;
}
inline void Link(int id,int p){
G[id].pb(p);//printf("%d->%d\n",id,p);
col[p]=col[id]^1;vis[p]=1;Q.push(p);
}
inline void link(int id,int l,int r){
q1.clear(),q2.clear();
q1.pb(id);
for(int i=l;i<=r;i++)q2.pb(all[i]);
if(!Query())return;
if(l==r)return void(Link(id,all[l]));
int mid=(l+r)>>1;
link(id,l,mid);link(id,mid+1,r);
}
int p1,p2;
inline int loc2(int l,int r,int l2,int r2,int S2){
if(l==r)return wa[l];
int mid=(l+r)>>1;qry.clear();
for(int i=l;i<=mid;i++)qry.pb(wa[i]);
int S1=query();
for(int i=l2;i<=r2;i++)qry.pb(wa[i]);
int S=query();
if(S>S1+S2)return loc2(l,mid,l2,r2,S2);
else return loc2(mid+1,r,l2,r2,S2);
}
inline void loc1(int l,int r,int S){
int mid=(l+r)>>1,S1,S2;
qry.clear();
for(int i=l;i<=mid;i++)qry.pb(wa[i]);
S1=query();qry.clear();
for(int i=mid+1;i<=r;i++)qry.pb(wa[i]);
S2=query();
if(S>S1+S2){
p1=loc2(l,mid,mid+1,r,S2);
p2=loc2(mid+1,r,p1,p1,0);
}else if(S1)loc1(l,mid,S1);
else loc1(mid+1,r,S2);
}
int dep[N],F[N];
inline void dfs(int x,int fa){
dep[x]=dep[fa]+1;F[x]=fa;
for(auto t:G[x])dfs(t,x);
}
vi R1,R2;
inline void solve(){
for(auto x:qry)wa.pb(x);
int S=query();
loc1(0,wa.size()-1,S);
dfs(1,0);if(dep[p1]<dep[p2])swap(p1,p2);
while(dep[p1]>dep[p2])
R1.pb(p1),p1=F[p1];
while(p1!=p2)R1.pb(p1),R2.pb(p2),p1=F[p1],p2=F[p2];
printf("N %d\n",R1.size()+R2.size()+1);
printf("%d ",p1);reverse(R1.begin(),R1.end());
for(auto x:R1)printf("%d ",x);
for(auto x:R2)printf("%d ",x);
fflush(stdout);exit(0);
}
int main(){
n=read();vis[1]=1;
getall();Q.push(1);
while(!Q.empty()&&!all.empty()){
int x=Q.front();Q.pop();
//printf("link %d\n",x);
link(x,0,all.size()-1);
getall();
}qry.clear();
for(int i=1;i<=n;i++)if(!col[i])qry.pb(i);
if(query())solve();qry.clear();
for(int i=1;i<=n;i++)if(col[i])qry.pb(i);
if(query())solve();qry.clear();
for(int i=1;i<=n;i++)if(col[i])qry.pb(i);
printf("Y %d\n",qry.size());
for(auto x:qry)printf("%d ",x);puts("");
return 0;
}