IOI '18 - Combo

#include "combo.h"

using namespace std;

string ch = "ABXY";

string guess_sequence(int N) {
  // Use 2 queries to find first character
  string p = "";
  for (int i = 0; i < 2*N; ++i) p += ch.substr(0, 2);
  int c1, c2;
  if (press(p)) c1 = 0, c2 = 1;
  else c1 = 2, c2 = 3;

  p = string(4*N, ch[c1]);
  if (!press(p)) swap(c1, c2);
  if (c1 != 0) swap(ch[0], ch[c1]);

  string S(1, ch[0]); // build the answer in this string

  // Use 1 query each for all remaining characters except last one
  for (int i = 1; i < N-1; ++i) {
    p = S + ch[2];
    for (int j = 1; j <= 3; ++j) p += S + ch[3] + ch[j];
    while ((int)p.size() < 4*N) p.push_back(ch[0]);

    int coins = press(p);
    if (coins == i) S.push_back(ch[1]);
    else if (coins == i+1) S.push_back(ch[2]);
    else S.push_back(ch[3]); // coins == i+2
  }

  // Use final 2 queries to find last character
  if (N > 1) {
    p = S + ch[1];
    while ((int)p.size() < 4*N) p.push_back(ch[0]);
    if (press(p) == N) S.push_back(ch[1]);
    else {
      p[N-1] = ch[2];
      if (press(p) == N) S.push_back(ch[2]);
      else S.push_back(ch[3]);
    }
  }
  return S;
}