Submission #963463

#	Time	Username	Problem	Language	Result	Execution time	Memory
963463		The_Samurai	Combo (IOI18_combo)	C++17	30 / 100	51 ms	600 KiB

combo

#include "combo.h"
#include "bits/stdc++.h"
using namespace std;

random_device rd;
mt19937_64 rng(rd());

void shuffle(string &s) {
  for (int i = 1; i < s.size(); i++) swap(s[rng() % (i + 1)], s[i]);
}

// 

string guess_sequence(int n) {
  string ans(n, '#'), s = "ABXY";
  vector can(vector(n, vector(4, '#')));
  for (int i = 0; i < n; i++) for (int j = 0; j < 4; j++) can[i][j] = s[j];
  auto get = [&](int i) -> char {
    return can[i][rng() % can[i].size()];
  };
  auto remove = [&](int i, char x) -> void {
    can[i].erase(find(can[i].begin(), can[i].end(), x));
  };
  for (int i = 0; i < 3; i++) {
    string t = ""; t += get(0);
    if (press(t)) {
      ans[0] = t[0];
      break;
    }
    remove(0, t[0]);
  }
  if (ans[0] == '#') ans[0] = get(0);
  for (int i = 1; i < n; i++) remove(i, ans[0]);
  int unknown = 0;
  while (unknown < n) {
    for (int i = unknown; i < n; i++) ans[i] = get(i);
    unknown = press(ans);
    if (unknown == n) break;
    remove(unknown, ans[unknown]);
  }
  return ans;
}

Compilation message (stderr)

combo.cpp: In function 'void shuffle(std::string&)':
combo.cpp:9:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |   for (int i = 1; i < s.size(); i++) swap(s[rng() % (i + 1)], s[i]);
      |                   ~~^~~~~~~~~~

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