Submission #923655

#	Time	Username	Problem	Language	Result	Execution time	Memory
923655		LucaLucaM	Combo (IOI18_combo)	C++17	100 / 100	14 ms	1892 KiB

combo

#ifndef COMBO_CPP_INCLUDED
#define COMBO_CPP_INCLUDED

#include "combo.h"
#include <vector>
#include <cassert>
#include <iostream>
#include <random>

std::mt19937 rng(0);

std::string str = "";
int NNN;

std::string guess_sequence(int n) {
  NNN = n;
  std::vector<std::string> alphabet = {"A", "B", "X", "Y"};
  std::string first = "";
  if (press("AB")) {
    if (press("A")) {
      first = "A";
    } else {
      first = "B";
    }
  } else {
    if (press("X")) {
      first = "X";
    } else {
      first = "Y";
    }
  }
  if (first.empty()) {
    first = alphabet.back();
  }
  if (n == 1) {
    return first;
  }
  int ptr = 0;
  while (alphabet[ptr] != first) {
    ptr++;
  }
  alphabet.erase(alphabet.begin() + ptr);
  str += first;
  for (int i = 1; i + 1 < n; i++) {
    std::string ask = str + alphabet[0];
    for (int i = 0; i < 3; i++) {
      ask += str + alphabet[1] + alphabet[i];
    }
    assert((int) ask.size() <= 4 * n);
    int ret = press(ask);
    if (ret == (int) str.size()) {
      str += alphabet[2];
    } else if (ret == 1 + (int) str.size()) {
      str += alphabet[0];
    } else {
      str += alphabet[1];
    }
  }
  for (int i = 0; i < 2; i++) {
    if (press(str + alphabet[i]) == 1 + (int) str.size()) {
      str += alphabet[i];
    }
  }
  if ((int) str.size() < n) {
    str += alphabet[2];
  }
  return str;
}


#endif // COMBO_CPP_INCLUDED

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