Submission #622832

#	Time	Username	Problem	Language	Result	Execution time	Memory
622832		jakubd	Combo (IOI18_combo)	C++17	30 / 100	140 ms	612 KiB

combo

#include <string>
#include <iostream>
#include <tuple>

using namespace std;

int press(std::string p);

tuple<char, char, char> remove_one(char c) {
  if (c == 'A') return make_tuple('B', 'X', 'Y');
  if (c == 'B') return make_tuple('A', 'X', 'Y');
  if (c == 'X') return make_tuple('A', 'B', 'Y');
  return make_tuple('A', 'B', 'X');
}

string guess_sequence(int N) {
  string res;

  // guess the first letter
  {
    if (press("AB")) {
      res += press("AX") ? 'A' : 'B';
    } else {
      res += press("AX") ? 'X' : 'Y';
    }
  }

  char A, B, C;
  tie(A, B, C) = remove_one(res[0]);

  for (int i = 1; i < N - 1; i++) {
    string a = res, b = res, c = res, d = res;
    a += A, b += A, c += A, d += B;
    a += A, b += B, c += C;
    string p = a + b + c + d;
    if (press(p) == i) {
      res += C;
    } else if (press(p) == i + 1) {
      res += B;
    } else {
      res += A;
    }
  }

  // guess the last letter
  if (N > 1) {
    string a = res, b = res;
    a += A, b += B;
    if (press(a + b) == N) {
      b.pop_back();
      res += press(a + b) == N ? A : B;
    } else {
      res += C;
    }
  }

  return res;
}

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