제출 #1223075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223075		madamadam3	Combo (IOI18_combo)	C++20	30 / 100	8 ms	508 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>

using namespace std;

using str = string;

#define rep(x) for (auto &x : CHARS)
#define each(x, a) for (auto &x : a)

default_random_engine rng;

str guess_sequence(int N) {
  rng = default_random_engine(chrono::system_clock::now().time_since_epoch().count());

  vector<str> CHARS = {"A", "B", "X", "Y"};
  shuffle(CHARS.begin(), CHARS.end(), rng);

  str fst = CHARS[0];
  for (int i = 1; i <= 3; i++) {
    if (press(CHARS[i]) == 1) {
      fst = CHARS[i];
      break;
    }
  }

  vector<string> nchars; for (int i = 0; i < 4; i++) if (CHARS[i] != fst) nchars.push_back(CHARS[i]);
  str pref = fst;

  while (pref.size() < N) {
    int curn = pref.size();

    bool found = false;
    shuffle(nchars.begin(), nchars.end(), rng);

    for (int k = 0; k <= 1; k++) {
      str guess_string = pref + nchars[k];
      if (curn + 1 <= N) guess_string += fst + pref + nchars[k] + nchars[k];
      if (curn + 2 <= N) guess_string += fst + pref + nchars[k] + nchars[k] + nchars[k];
      int ans = press(guess_string);
      
      if (ans <= curn) continue;
      found = true;
      
      pref += nchars[k];
      if (ans >= curn + 2) pref += nchars[k];
      if (ans >= curn + 3) pref += nchars[k];
      break;
    }

    if (found == false) pref += nchars[2];
  }

  return pref;
}

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