Submission #923632

#	Time	Username	Problem	Language	Result	Execution time	Memory
923632		LucaLucaM	Combo (IOI18_combo)	C++17	30 / 100	23 ms	1928 KiB

combo

#ifndef COMBO_CPP_INCLUDED
#define COMBO_CPP_INCLUDED

#include "combo.h"
#include <vector>
#include <cassert>
#include <iostream>

std::string str = "";
int NNN;

std::string get(std::vector<std::string> v) {
  if ((int) v.size() == 1) {
    return v[0];
  }
  int n = (int) v.size();
  std::vector<std::string> lt, rt;
  for (int i = 0; i < n / 2; i++) {
    lt.push_back(v[i]);
  }
  for (int i = n / 2; i < n; i++) {
    rt.push_back(v[i]);
  }
  std::string ask = "";
  for (const auto &s : lt) {
    ask += str + s;
  }
  assert((int) lt.size() <= (int) rt.size());
  assert((int) ask.size() <= 4 * NNN);
  if (press(ask) == (int) str.size() + (int) lt[0].size()) {
    return get(lt);
  } else {
    return get(rt);
  }
}

std::vector<std::string> bkt(std::vector<std::string> alphabet, int len) {
  if (len == 1) {
    return alphabet;
  }
  std::vector<std::string> ret;
  std::vector<std::string> aux = bkt(alphabet, len - 1);
  for (int i = 0; i < (int) alphabet.size(); i++) {
    for (const auto &q : aux) {
      ret.push_back(alphabet[i] + q);
    }
  }
  return ret;
}

std::string guess_sequence(int n) {
  NNN = n;
  std::vector<std::string> alphabet = {"A", "B", "X", "Y"};
  std::string first = "";
  for (int i = 0; i < 3; i++) {
    if (press(alphabet[i])) {
      first = alphabet[i];
      break;
    }
  }
  if (first.empty()) {
    first = alphabet.back();
  }
  int ptr = 0;
  while (alphabet[ptr] != first) {
    ptr++;
  }
  int p3[8] = {};
  p3[0] = 1;
  for (int i = 1; i < 8; i++) {
    p3[i] = 3 * p3[i - 1];
  }
  alphabet.erase(alphabet.begin() + ptr);
  str += first;
  for (int i = 1; i < n;) {
    for (int len = 7; len > 0; len--) {
      if ((long long) ((int) str.size() + len) * (p3[len] / 2) > 4 * n) {
        continue;
      }
      std::vector<std::string> cand = bkt(alphabet, len);
      str += get(cand);
      i += len;
      break;
    }
  }
  return str;
}


#endif // COMBO_CPP_INCLUDED

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