Submission #26822079

---

Source Code Expand

//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#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<'0'||c>'9';c=getchar()) if(c=='-') f=1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(f) x=-x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
int n,a,b,fa[100005],sz[100005],rs[100005];queue<int>q;
#ifndef ONLINE_JUDGE
int limit=0;char debug[100005];mt19937 rnd(time(0));
#endif
inline char qry(int x,int y)
{
#ifdef ONLINE_JUDGE
	printf("? %d %d\n",x-1,y-1),fflush(stdout);
	char ch[4];scanf("%s",ch);return *ch=='Y';
#else
	limit++;if(debug[x]) return debug[y];
	else return 0;
#endif
}
inline int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}
int main()
{
#ifdef ONLINE_JUDGE
	read(a,b),n=a+b;
#else
	scanf("%s",debug+1),n=strlen(debug+1);
	for(int i=1;i<=n;i++) debug[i]^=48;
	for(int i=1;i<=n;i++) a+=debug[i],b+=!debug[i];
#endif
	if(a<=b) return puts("Impossible"),0;
	for(int i=1;i<=n;i++) fa[i]=i,q.push(i);
	memset(rs,-1,sizeof(rs));int la;
	while((int)q.size()>1)
	{
		int x=q.front(),y;q.pop(),y=q.front();q.pop();
		if(q.empty()) {la=(sz[x]>sz[y]?x:y);break;}
		char a=qry(x,y),b=qry(y,x);
		if(a&&b) fa[x]=y,q.push(y),sz[y]+=sz[x];
		else if(a||b) rs[a?x:y]=0,q.push(a?y:x);
	}
	int hn;rs[hn=q.empty()?la:q.front()]=1;
	for(int i=1;i<=n;i++) if(!~rs[i]&&getf(i)==i) rs[i]=qry(hn,i);
	for(int i=1;i<=n;i++) if(!~rs[i]) rs[i]=rs[getf(i)];
#ifndef ONLINE_JUDGE
	printf("cnt = %d\nlimit = %d\n",limit,n*2);
	for(int i=1;i<=n;i++) if(rs[i]^debug[i]) return puts("Fail"),0;
	return puts("Succeed"),0;
#else
	printf("! ");for(int i=1;i<=n;i++) putchar(rs[i]^48);
	return putchar('\n'),fflush(stdout),0;
#endif
}

Submission Info

Compile Error

./Main.cpp: In function ‘char qry(int, int)’:
./Main.cpp:20:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   20 |  char ch[4];scanf("%s",ch);return *ch=='Y';
      |             ~~~~~^~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:19:8: warning: ‘la’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   19 |  printf("? %d %d\n",x-1,y-1),fflush(stdout);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
./Main.cpp:38:31: note: ‘la’ was declared here
   38 |  memset(rs,-1,sizeof(rs));int la;
      |                               ^~

Judge Result