Language: C++

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<random>

//std::random_device seed_gen;
//std::mt19937 engine(seed_gen());
//std::uniform_int_distribution<int> dN(10,128);
//std::uniform_int_distribution<int> dN(10,10);
//std::uniform_int_distribution<int> dC(0,61);

char ch[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
char buf[130];
//char ans[129];
int len;

#if 0
void gen_ans() {
  static bool first = true;
  if(!first) return;
  first = false;
  int N = dN(engine);
  ans[N] = 0;
  for(int i = 0; i < N; ++i) ans[i] = ch[dC(engine)];
  std::cout << "ans = [" << ans << "]\n";
}
#endif

int dp[2][128];
int edit_distance(char const*s1, char const*s2) {
  int i, j;
  dp[0][0] = 0;
  for(i = 1; s1[i-1]; ++i) dp[0][i] = i;
  for(j = 1; s2[j-1]; ++j) {
    dp[j%2][0] = j;
    for(i = 1; s1[i-1]; ++i) {
      dp[j%2][i] = std::min(std::min(dp[(j-1)%2][i], dp[j%2][i-1]) + 1,
        dp[(j-1)%2][i-1] + (s1[i-1] == s2[j-1]? 0: 1));
    }
  }
  return dp[(j-1)%2][i-1];
}


int trybuf() {
  std::cout << buf << std::endl;
#if 1
  int a; std::cin >> a; 
#else
  //int a = edit_distance("Atcod3rIsGreat", buf+1);
  int a = edit_distance("fO58XmTmum", buf+1);
  //gen_ans();
  //int a = edit_distance(ans, buf+1);
  std::cout << a << "\n\n";
#endif
  if(a == 0) {
    buf[0] = '!';
    std::cout << buf << std::endl;
    exit(0);
  }
  return a;
}

int try_anb(char a, int n, char b) {
  for(int i = 0; i < n; ++i) buf[i+1] = a;
  for(int i = n; i < len; ++i) buf[i+1] = b;
  return trybuf();
}

int num['z'+1][129][129];

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  buf[0] = '?';
  buf[129] = 0;
  len = 0;
  std::vector<char> v;
  for(char c: ch) if(c != 0) {
    for(int i = 0; i <= 128; ++i) std::fill_n(num[c][i], 129, 0);
    for(int j = 0; j < 128; ++j) buf[j+1] = c;
    int l = 128 - trybuf();
    len += l;
    if(l > 0) { 
      v.push_back(c);
      num[c][0][128] = l;
    }
  }
  if(len < 128) for(char c: v) num[c][0][len] = num[c][0][128];
  buf[len+1] = 0;
  for(int w = 128; w > 1; w/= 2) if(w/2 < len) {
    if(w >= len) {
      int m = w/2;
      int sum = 0;
      for(int i = 1; i < v.size(); ++i) {
        int k = len - try_anb(v[0], m, v[i]) - num[v[i]][0][len];
        num[v[i]][0][m] = -k;
        sum -= k;
      }
      assert( (m-sum)%v.size() == 0);
      int na = (m-sum)/v.size();
      for(char c: v) { 
        num[c][0][m] += na;
        num[c][m][len] = num[c][0][len] -  num[c][0][m];
      }
    } else {
      int m = w/2;
      for(int l = 0; l+m < len; l += w) {
        int ww = std::min(w, len-l);
        std::vector<char> vv;
        for(char c: v) if(num[c][l][l+ww] > 0) vv.push_back(c);
        int sum = 0;
        for(int i = 1; i < vv.size(); ++i) {
          int k = len - try_anb(vv[0], l+m, vv[i]) - num[vv[0]][0][l] - num[vv[i]][l+ww][len];
          k = num[vv[i]][l][l+ww] - k;
          num[vv[i]][l][l+m] = k;
          sum += k;
        }
        assert( (m-sum)%vv.size() == 0);
        int na = (m-sum)/vv.size();
        for(char c: vv) {
          num[c][l][l+m] += na;
          num[c][l+m][l+ww] = num[c][l][l+ww] - num[c][l][l+m];
          num[c][0][l+m] = num[c][0][l] + num[c][l][l+m];
          num[c][l+m][len] = num[c][l+m][l+ww] + num[c][l+ww][len];
        }
      }
    }
  }
  for(int i = 0; i < len; ++i) {
    for(char c: v) if(num[c][i][i+1] > 0) {
      buf[i+1] = c; break;
    }
  }
  trybuf();
  
  return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:100:7: error: 'assert' was not declared in this scope
  100 |       assert( (m-sum)%v.size() == 0);
      |       ^~~~~~
a.cc:6:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    5 | #include<random>
  +++ |+#include <cassert>
    6 | 
a.cc:119:9: error: 'assert' was not declared in this scope
  119 |         assert( (m-sum)%vv.size() == 0);
      |         ^~~~~~
a.cc:119:9: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'