Submission #676036

#	Time	Username	Problem	Language	Result	Execution time	Memory
676036		Hegdahl	Combo (IOI18_combo)	C++17	100 / 100	36 ms	648 KiB

combo

#include "combo.h"

#include <bits/stdc++.h>

using namespace std;

string guess_sequence(int n) {
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

  char starter = '?';
  if (press("AB")) {
    if (press("A"))
      starter = 'A';
    else
      starter = 'B';
  } else if (press("X"))
    starter = 'X';
  else
    starter = 'Y';

  string abc;
  for (char ch : {'A', 'B', 'X', 'Y'})
    if (ch != starter) abc += ch;
  assert(abc.size() == 3);
  char a = abc[0];
  char b = abc[1];
  char c = abc[2];

  string ans = {starter};
  while ((int)ans.size() < n) {
    if ((int)ans.size() + 1 == n) {
      int r = uniform_int_distribution(0, 2)(rng);
      if (press(ans + abc[r]) - (int)ans.size()) {
        ans += abc[r];
      } else if (press(ans + abc[(r + 1) % 3]) - (int)ans.size()) {
        ans += abc[(r + 1) % 3];
      } else {
        ans += abc[(r + 2) % 3];
      }

      continue;
    }

    int qa = press(ans + a + a + ans + a + b + ans + a + c + ans + b) - (int)ans.size();
    if (qa == 0) ans += c;
    else if (qa == 1) ans += b;
    else if (qa == 2) ans += a;
    else assert(0);
  }

  return ans;
}

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