Submission #526043

#	Time	Username	Problem	Language	Result	Execution time	Memory
526043		benjaminkleyn	Combo (IOI18_combo)	C++17	100 / 100	30 ms	764 KiB

combo

#include "combo.h"

std::string guess_sequence(int N) {
  std::string S;
  std::string pos;
  int coins;

  // find first letter (2 presses)
  if (press("AB")) 
  {
    if (press("A")) 
      pos = "BXY", S = "A";
    else 
      pos = "AXY", S = "B";
  }
  else if (press("X")) 
    pos = "ABY", S = "X";
  else 
    pos = "ABX", S = "Y";


  // find next N-2 letters (N-2 presses)
  for (int i = 1; i < N - 1; i++)
  {
      // the length of this string will always be < 4N.
      coins = press(S + pos[0] + pos[0] + S + pos[0] + pos[1] + S + pos[0] + pos[2] + S + pos[1]);
      // 'i' is current length of S
      if (coins == i + 2)
        S += pos[0];
      else if (coins == i + 1)
        S += pos[1];
      else if (coins == i)
        S += pos[2];
  }

  // find last letter (2 presses)
  if (N > 1)
  {
    if (press(S+pos[0]) == N) S+=pos[0];
    else if (press(S+pos[1]) == N) S+=pos[1];
    else S+=pos[2];
  }

  return S;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95