Problem:
 Score : 1100 points    Problem Statement This is an interactive task.  You have to guess a secret password S . 
A password is a nonempty string whose length is at most L . 
The characters of a password can be lowercase and uppercase english letters (a, b, ... , z, A, B, ... , Z) and digits (0, 1, ... , 9).  In order to guess the secret password S you can ask queries.
A query is made of a valid password T , the answer to such query is the edit distance between S and T (the operations considered for the edit distance are: removal, insertion, substitution).
You can ask at most Q queries.  Note : For a definition of edit distance (with operations: removal, insertion, substitution), see this wikipedia page .      Constraints  L = 128  Q = 850  The secret password S is chosen before the beginning of the interaction.       Interaction To ask a query, print on Standard Output (with a newline at the end)  ? T   The string T must be a valid password.  The answer ans to each query shall be read from Standard Input in the form:  ans   As soon as you have determined the hidden password S , you should print on Standard Output (with a newline at the end)  ! S   and terminate your program.      Judgement  After each output, you must flush Standard Output. Otherwise you may get TLE .  After you print (your guess of) the hidden password, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.  If the password you have determined is wrong, you will get WA .  If you ask a malformed query (for example because the string is not a valid password, or you forget to put ? ) or if your program crashes or if you ask more than Q queries, the behavior of the judge is undefined (it does not necessarily give WA ).       Samples In the only sample testcase of this problem the hidden password is Atcod3rIsGreat .  The following one is an example of interaction if S= Atcod3rIsGreat .     Input  Output       \texttt{? AtcoderIsBad}    5      \texttt{? AtcoderIsGreat}    1      \texttt{! Atcod3rIsGreat}

Solution (Python):
import string
from heapq import heapify, heappop, heappush


def judge():
    import Levenshtein
    import subprocess

    ans = 'OQqZbgyIYiB59fqHVsXu0PZVEWy1sApStRxCJFMeNkr5O0U4jEX9ksBTpKw7Z3ylYd3Hnd'
    query_count = 0
    with subprocess.Popen(['python', __file__, 'EXE'],
                          stdin=subprocess.PIPE,
                          stdout=subprocess.PIPE,
                          stderr=subprocess.PIPE) as p:
        while True:
            query = p.stdout.readline().decode().strip()
            print(query)
            if query[0] == '?':
                d = Levenshtein.distance(query[2:], ans)
                print(d)
                p.stdin.write(f'{d}\n'.encode())
                p.stdin.flush()
                query_count += 1
            elif query[0] == '!':
                print(query[2:] == ans)
                print(query_count)
                break
            else:
                pass









STR = string.ascii_letters + string.digits
counter = {}
for c in STR:
    print(f'? {c * 128}')
    a = int(input())
    if a == 128:
        continue
    counter[c] = 128 - a

l = sum(counter.values())
q = [(cnt, [c] * cnt) for c, cnt in counter.items()]
heapify(q)

while len(q) > 1:
    l1, t1 = heappop(q)
    l2, t2 = heappop(q)
    i = 0
    j = 0
    while i < len(t1) and j < l2:
        t1.insert(i, t2[j])
        s = ''.join(t1)
        print(f'? {s}')
        a = int(input())
        if len(t1) > l - a:
            t1.pop(i)
        else:
            j += 1
        i += 1
    if j < len(t2):
        t1.extend(t2[j:])

    heappush(q, (l1 + l2, t1))

_, t = q[0]
s = ''.join(t)
print(f'! {s}')

Solution (Python):
def Q(x):
    print("?",x,flush=True)
    return int(input())

x=Q("A")
if x==128:
    L=128
else:    
    y=Q("A"*x)
    z=Q("A"*(x+1))

    if z==y:
        L=x+1
    else:
        L=x

S=[chr(i) for i in range(48,58)]+[chr(i) for i in range(65,91)]+[chr(i) for i in range(97,123)]
K=[-1]*62

for i in range(62):
    K[i]=L-Q(S[i]*L)

import heapq
A=[(K[i],S[i]*K[i]) for i in range(62)]
heapq.heapify(A)

while len(A)>1:
    x,y=heapq.heappop(A)
    if x==0:
        continue
    z,w=heapq.heappop(A)

    ind=0
    for i in range(len(w)):
        while Q(y[:ind]+w[i]+y[ind:])>=L-x-i:
            ind+=1
        y=y[:ind]+w[i]+y[ind:]
        ind+=1
    heapq.heappush(A,(x+z,y))
    
print("!",A[0][1],flush=True)

Solution (Python):
def Q(x):
    print("?",x,flush=True)
    return int(input())

x=Q("A")
if x==128:
    L=128
else:    
    y=Q("A"*x)
    z=Q("A"*(x+1))

    if z==y:
        L=x+1
    else:
        L=x

S=[chr(i) for i in range(48,58)]+[chr(i) for i in range(65,91)]+[chr(i) for i in range(97,123)]
K=[-1]*62

for i in range(62):
    K[i]=L-Q(S[i]*L)

import heapq
A=[(K[i],S[i]*K[i]) for i in range(62)]
heapq.heapify(A)

while A[0][0]==0:
    heapq.heappop(A)

while len(A)>1:
    x,y=heapq.heappop(A)
    z,w=heapq.heappop(A)

    ind=0
    for i in range(len(w)):
        while Q(y[:ind]+w[i]+y[ind:])>=L-x-i:
            ind+=1
        y=y[:ind]+w[i]+y[ind:]
        ind+=1
    heapq.heappush(A,(x+z,y))
    
print("!",A[0][1],flush=True)

Solution (Python):
import string
LTRS = string.ascii_letters + string.digits
MAXL = 128

def query(s):
    print('?', s)
    r = int(input())
    if r==0:
        print('!', s)
        exit()
    return r

import heapq
hq = []
heapq.heapify(hq)
for c in LTRS:
    r = query(c * MAXL)
    l = MAXL - r
    if l:
        heapq.heappush(hq, (l, c*l))

def merge(s,t):
    cost = query(s)
    ret = ''
    i = j = 0
    while i < len(s) and j < len(t):
        r = query(ret + t[j] + s[i:])
        if r < cost:
            cost = r
            ret += t[j]
            j += 1
        else:
            ret += s[i]
            i += 1
    if i == len(s):
        ret += t[j:]
    elif j == len(t):
        ret += s[i:]
    else:
        assert False
    return ret

while len(hq) >= 2:
    _,s = heapq.heappop(hq)
    _,t = heapq.heappop(hq)
    u = merge(s,t)
    heapq.heappush(hq, (len(u), u))

_,ans = heapq.heappop(hq)
query(ans)

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc044/tasks/agc044_d

文字数はわかる
どの文字がいくつあるかは分かる
a文字入ってたとすると
128-|S| + |S|-a = 128-a = rep
a = 128-rep

文字列のマージを考える
同じ文字はまとめて扱ったほうが良い？
大きい方を小さい方に融合することを考える

aaaa + bbb → aabbaba
にすることを考えてみようか

aaaa → 3
aabaa
左側の文字列に右の文字列を前から入れていく
入れる場所が正しければ回数は減る

2分割していけばマージ計算量でO(nlogn)!
128 + log128 + log128

マージ部分が違うっポイ？
同じ文字が両方に交じってると面倒なことになる
小さい方からマージ？
"""

def merge(L,R):

    if len(L) > len(R):
        tmp = L
        L = R
        R = tmp

    

    if len(R) > 1:
        print ("?","".join(R),flush=True)
        origin = int(input())
    else:
        origin = len(s)-1

    ok = []
    while len(L) > 0 and len(R) > 0:
        
        q = ok + [ L[0] ] + R
        if len(q) > 1:
            print ("?" , "".join(q) , flush=True)
            now = int(input())
        else:
            now = len(s)-1

        if now < origin:
            ok.append(L[0])
            del L[0]
            origin = now
        else:
            ok.append(R[0])
            del R[0]

    if len(L) > 0:
        ok = ok + L
    if len(R) > 0:
        ok = ok + R

    return ok


import heapq

alp = "abcdefghjiklmnopqrstuvwxyz"
ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
NUM = "0123456789"

ss = alp+ALP+NUM

    
dic = {}
q = []
s = ""

for i in ss:

    print ("?",i*128,flush=True)
    ret = int(input())
    tmp = list(i * (128-ret))
    heapq.heappush (q , ( 128-ret , tmp ) )
    s += i*(128-ret)

while len(q) >= 2:

    alen,astr = heapq.heappop(q)
    blen,bstr = heapq.heappop(q)

    cat = merge(astr,bstr)
    heapq.heappush(q , (alen+blen , cat))

print ("!","".join(q[0][1]))

Solution (Python):
import sys
import random
import string

DEBUG = False
secret_str = "Atcod3rIsGreat"
count = 0


def local_str(query : str) -> int:
    import Levenshtein
    return Levenshtein.distance(query , secret_str)


def query_str(query : str) -> int:
    global count
    count += 1
    if DEBUG:
        ans = local_str(query)
        return ans
    else:
        print("? " + query)
        ans = int(input())
        if ans == 0:
            print("! " + query)
            sys.exit(0)
        return ans

def guess_length() -> int:
    c = "a"
    a = query_str(c)
    if a == 128:
        return 128
    al = query_str(c * a)
    al2 = query_str(c * (a + 1))
    if al >= al2:
        return a + 1
    else:
        return a


def merge(S : str, T : str) -> str:
    t = 0
    len_t = len(T)
    d = query_str(T)
    for s, c in enumerate(S):
        while t < len_t:
            l = T[:t +s]
            r = T[s + t:]
            d2 = query_str(l + c + r)
            if d2 < d:
                T = l + c + r
                d = d2
                break
            t += 1
        if t == len_t:
            T = T + c
    return T

def guessing():
    password_len = guess_length()
    chars = []
    for c in string.ascii_letters + string.digits:
        unmatch_word_num = query_str(c * password_len)
        if password_len - unmatch_word_num > 0:
            chars.append(c * (password_len - unmatch_word_num))
    while len(chars) > 1:
        chars.sort(key=lambda x: len(x))
        m = merge(chars[0], chars[1])
        chars[1] = m
        chars = chars[1:]
    query_str(chars[0])
    return chars[0]


guessing()
def randomname(n):
   randlst = [random.choice(string.ascii_letters + string.digits) for i in range(n)]
   return ''.join(randlst)

Solution (Python):
import sys

L = 128

chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

count_table = {}
sub_passwords = []
length = 0
for i, c in enumerate(chars):
	print("? " + (c * L), flush = True)
	l = L - int(input())
	if l > 0:
		count_table[c] = l
		sub_passwords.append(c * l)
	length += l



def merge(a, b):

	fixed = ""
	while True:

		pw = fixed + b[0] + a
		print("? " + pw, flush = True)

		led = int(input())

		if led == length - len(pw):
			fixed += b[0]
			b = b[1:]
			if len(b) == 0:
				break
		else:
			fixed += a[0]
			a = a[1:]
			if len(a) == 0:
				break

	print("fixed: {}-{}-{}".format(fixed, a, b) , flush = True, file = sys.stderr)
	return fixed + a + b

import heapq

queue = []
for sub_password in sub_passwords:
	heapq.heappush(queue, (len(sub_password), sub_password))

while len(queue) > 1:
	l_a, a = heapq.heappop(queue)
	l_b, b = heapq.heappop(queue)
	heapq.heappush(queue, (l_a + l_b, merge(a, b)))


print("! " + queue[0][1])