Submission #1117954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117954		blackslex	Combo (IOI18_combo)	C++17	100 / 100	53 ms	2140 KiB

combo

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

using namespace std;

std::string guess_sequence(int N) {
  string s = "";
  vector<char> c{'A', 'B', 'X', 'Y'};
  multiset<char> ms;
  bool f = 0;
  char x;
  if (press("AB")) {
    if (press("A")) x = 'A';
    else x = 'B';
  } else {
    if (press("X")) x = 'X';
    else x = 'Y';
  }
  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);
  };
  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: 95 / 95