简短交互代码求调
查看原帖
简短交互代码求调
140876
syzf2222楼主2022/7/4 16:39

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;
}
2022/7/4 16:39
加载中...