Problem:
 Score : 1300 points    Problem Statement This is an interactive task.  AtCoDeer the deer came across N people. For convenience, the people are numbered 0 through N-1 .
Among them, A are honest and the remaining B(=N-A) are unkind .
All of these N people know who are honest and who are unkind, but AtCoDeer only knows that there are A honest and B unkind people.
He is trying to identify all of the honest people by asking questions to these N people.
For one question, AtCoDeer selects a and b  (0≤a,b≤N-1) , and asks person a the following question: "Is person b honest?"  An honest person will always answer correctly by "Yes" or "No".
An unkind person, however, will answer by selecting "Yes" or "No" arbitrarily .
That is, the algorithm used by an unkind person may not be simple one such as always lying or giving random fifty-fifty answers.  AtCoDeer can ask at most 2N questions. He will ask questions one by one, and the responses to the previous questions can be used when deciding the next question to ask.  Identify all of the honest people.
If it is impossible (more formally, if, for any strategy of asking 2N questions, there exists a strategy for unkind people to answer the questions so that there are two or more possible sets of the honest people), report that fact.      Constraints  1≤A,B≤2000       Input and Output First, A and B are given from Standard Input in the following format:  A  B   If identifying the honest people is impossible, the program must immediately print the following output and terminate itself:  Impossible  Otherwise, the program shall ask questions.
Each question must be written to Standard Output in the following format:  ? a  b   Here, a and b must be integers between 0 and N-1 (inclusive).
The response to the question will be given from Standard Input in the following format:  ans   Here, ans is either Y or N . Y represents "Yes"; N represents "No".  Finally, the answer must be written to Standard Output in the following format:  ! s_0s_1...s_{N-1}   Here, s_i must be 1 if person i is honest, and 0 if person i is unkind.      Judgement  After each output, you must flush Standard Output. Otherwise you may get TLE .  After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.  When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA ).       Samples In the following sample, A = 2 , B = 1 , and the answer is 101 .     Input  Output      2  1      ?  0  1    N      ?  0  2    Y      ?  1  0    Y      ?  2  0    Y      ?  2  2    Y      !  101     In the following sample, A = 1 , B = 2 , and the answer is Impossible .     Input  Output      1  2      Impossible

Solution (Python):
A, B = map(int, input().split(" "))

if A <= B:
    print("Impossible")
    exit(0)

chain = []
N = A + B

def ask(i, j):
    print("? %d %d" % (i, j))
    return input() == 'Y'

for i in range(0, N):
    if len(chain) == 0:
        chain.append(i)
        continue
    last = chain[-1]
    if ask(last, i):
        chain.append(i)
    else:
        chain.pop()

main = chain.pop()
ret = [ ('1' if ask(main, x) else '0') for x in range(0, N) ]

print("! %s" % ("".join(ret)))

Solution (Python):
A, B = map(int, input().split())
N = A + B
X = [i for i in range(N)]
Y = []
def chk(a, b):
    print("?", a, b)
    return 1 if input() == "Y" else 0
if A <= B:
    print("Impossible")
else:
    while X:
        if not Y:
            Y.append(X.pop())
        else:
            if chk(Y[-1], X[-1]):
                Y.append(X.pop())
            else:
                X.pop()
                Y.pop()
    print("!", "".join([str(chk(Y[-1], i)) for i in range(N)]))

Solution (Python):


import bisect
import sys

(a, b) = tuple(map(int, input().split(' ')))

if a <= b:
    print("Impossible")
    sys.exit()

n = a + b

def ask(i, j):
    print("? ", i, j)
    ans = input()
    if ans == 'Y':
        return True
    elif ans == 'N':
        return False

path = []
nlen = b + 1
for i in range(n):
    if len(path) == 0:
        path.append(i)
        if len(path) >= nlen:
            break
    else:
        if ask(path[-1], i):
            path.append(i)
            if len(path) >= nlen:
                break
        else:
            path.pop()
            nlen -= 1
    
            
o1 = path[-1]

result = ''
for i in range(n):
    if i != o1:
        if ask(o1, i):
            result += '1'
        else:
            result += '0'            
    else:
        result += '1'        

print('!', result)

Solution (Python):
from collections import *
p,i=print,input
q=lambda *a:(p('?',*a),i()=='Y')[1]
A,B=map(int,i().split())
r=range(A+B)
c=deque(r)
if A>B:
	while len(c)>2:c.extendleft(([],[c[-2]])[q(c.pop(),c.pop())])
	p('!',''.join(str(int(q(c[0],d))) for d in r))
else: p('Impossible')

Solution (Python):
import collections,sys
p=print
def ask(x,y):
	p('?',x,y)
	return input()=='Y'
A,B=map(int,input().split())
r=range(A+B)
if A<=B:
	p('Impossible')
	sys.exit()
c=collections.deque(r)
while len(c)>2:
	x,y=c.pop(),c.pop()
	if ask(x,y):
		c.appendleft(y)
p('!',''.join(str(int(ask(c[0],i))) for i in r))

Solution (Python):
import sys
from collections import deque

A,B = map(int,input().split())
ask = lambda x,y: print('?',x,y, flush=True)

if A <= B:
  print('Impossible', flush=True)
  sys.exit()

N = A+B
candidates = deque(range(N), N)

while len(candidates) > 2:
  x,y = candidates.pop(), candidates.pop()
  ask(x,y)
  if input() == 'Y':
    candidates.appendleft(y)

god = candidates[0]
result = []
for i in range(N):
  ask(god,i)
  result.append(input() == 'Y')

print('!', ''.join(str(int(s)) for s in result), flush=True)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def pf(s):
    print(s, flush=True)

def main():
    a,b = LI()
    if a <= b:
        return 'Impossible'

    l = []
    for i in range(a+b):
        if not l:
            l.append(i)
            continue
        pf('? {} {}'.format(i,l[-1]))
        if S() == 'Y':
            l.append(i)
        else:
            l = l[:-1]

    r = []
    ai = l[0]
    for i in range(a+b):
        if i == ai:
            r.append('1')
            continue
        pf('? {} {}'.format(ai,i))
        if S() == 'Y':
            r.append('1')
        else:
            r.append('0')

    return '! {}'.format(''.join(r))


print(main(), flush=True)