Submission #285821

#	Time	Username	Problem	Language	Result	Execution time	Memory
285821		ipaljak	Combo (IOI18_combo)	C++14	100 / 100	41 ms	672 KiB

combo

#include "combo.h"

#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<

string guess_sequence(int N) {
  string ret = "";
  if (N == 1) {
    if (press("A")) return "A";
    if (press("B")) return "B";
    if (press("X")) return "X";
    return "Y";
  }

  int x = press("AB");
  if (x == 2) {
    ret = "A";
  }
  if (x == 1) {
    int y = press("A");
    if (y) ret = "A"; else ret = "B";
  }
  if (x == 0) {
    int y = press("X");
    if (y) ret = "X"; else ret = "Y";
  }

  string B = "";
  for (char c : "ABXY")
    if (c != ret[0]) B.push_back(c);

  for (int i = ret.size(); i < N - 1; ++i) {
    string guess = "";
    for (int j = 0; j < 3; ++j) {
      guess += ret;
      guess.push_back(B[0]);
      guess.push_back(B[j]);
    }
    guess += ret;
    guess.push_back(B[1]);
    int x = press(guess);
    assert(x >= i);
    ret.push_back(B[2 - (x - i)]);
  }

  ret.push_back(B[0]);
  if (press(ret) == N) return ret;

  ret.pop_back();
  ret.push_back(B[1]);
  if (press(ret) == N) return ret;

  ret.pop_back();
  ret.push_back(B[2]);
  return ret;
}

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