Submission #1117953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117953		blackslex	Combo (IOI18_combo)	C++17	97 / 100	54 ms	2064 KiB

combo

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

using namespace std;

mt19937 rng(time(nullptr));

std::string guess_sequence(int N) {
  string s = "";
  vector<char> c{'A', 'B', 'X', 'Y'};
  multiset<char> ms;
  bool f = 0;
  for (auto &e: c) ms.emplace(e);
  char x;
  while (ms.size() > 1) {
    char e = *ms.begin(); ms.erase(ms.begin());
    string p; p.push_back(e);
    if (press(p)) {x = e; f = 1; break;}
  }
  if (!f) x = *ms.begin();
  s = string(1, x);
  auto pos = find(c.begin(), c.end(), x);
  c.erase(pos, pos + 1);
  auto get = [&] (char x) {
    return string(1, x);
  };
  auto get2 = [&] (int x) {
    return rng() % x;
  };
  random_shuffle(c.begin(), c.end(), get2);
  vector<string> cs{get(c[0]), get(c[1]) + get(c[0]), get(c[1]) + get(c[1]), get(c[1]) + get(c[2])};
  for (int i = 2; i < N; i++) {
    string p = "";
    for (auto &e: cs) p += s + e;
    int k = press(p);
    if (k == i) s.push_back(c[0]);
    else if (k == i + 1) s.push_back(c[1]);
    else s.push_back(c[2]);
  }
  if (N != 1) {
    ms.clear();
    for (auto &e: c) ms.emplace(e);
    f = 0;
    while (ms.size() > 1) {
      char e = *ms.begin(); ms.erase(ms.begin());
      string p = s; p.push_back(e);
      if (press(p) == N) {x = e; f = 1; break;}
    }
    if (!f) x = *ms.begin();
    s.push_back(x);
  }
  return s;
}

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