제출 #1223085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223085		madamadam3	Combo (IOI18_combo)	C++20	100 / 100	7 ms	484 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];
  
  if (N == 1) {
    for (int i = 1; i <= 3; i++) {
      if (press(CHARS[i]) == 1) {
        fst = CHARS[i];
        break;
      }
    }
  } else {
    if (press("AB") >= 1) {
      fst = press("A") == 1 ? "A" : "B";
    } else {
      fst = press("X") == 1 ? "X" : "Y";
    }
  }

  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);

    if (curn >= N-1) {
      if (press(pref + nchars[0]) > curn) {
        found = true;
        pref += nchars[0];
      } else if (press(pref + nchars[1]) > curn) {
        found = true;
        pref += nchars[1];
      }
    } else {
      string gs = pref + nchars[0] + fst + 
                  pref + nchars[1] + nchars[0] +
                  pref + nchars[1] + nchars[1] + 
                  pref + nchars[1] + nchars[2];

      int ans = press(gs);
      if (ans == curn+1) {
        pref += nchars[0];
        found = true;
      } else if (ans == curn+2) {
        pref += nchars[1];
        found = true;
      }
    }

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

  return pref;
}

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