Submission #1756052

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

bool query(int u, int v)
{
	cout<<"? "<<u<<' '<<v<<'\n';
	fflush(stdout);
	char c; cin>>c;
	return (c=='Y'?1:0);
}

bool good[2111];

int main()
{
	int a,b; cin>>a>>b;
	if(b>=a){cout<<"Impossible\n"; fflush(stdout); return 0;}
	stack<int> s;
	s.push(0);
	for(int i=1;i<a+b;i++)
	{
		if(s.empty())
		{
			s.push(i); continue;
		}
		int tmp=query(s.top(),i);
		if(!tmp)
		{
			s.pop();
		}
		else
		{
			s.push(i);
		}
	}
	for(int i=0;i<a+b;i++)
	{
		good[i]=query(s.top(),i);
	}
	cout<<"! ";
	for(int i=0;i<a+b;i++) cout<<good[i];
	cout<<'\n'; fflush(stdout);
}

Submission Info

Judge Result