Submission #622833

#	Time	Username	Problem	Language	Result	Execution time	Memory
622833		jakubd	Combo (IOI18_combo)	C++17	100 / 100	39 ms	664 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;
    int ans = press(p);
    if (ans == i) {
      res += C;
    } else if (ans == 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: 95 / 95