Submission #923624

#	Time	Username	Problem	Language	Result	Execution time	Memory
923624		LucaLucaM	Combo (IOI18_combo)	C++17	30 / 100	20 ms	1900 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) ask.size() <= 4 * NNN);
  if (press(ask) == (int) str.size() + (int) lt[0].size()) {
    return get(lt);
  } else {
    return get(rt);
  }
}

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++;
  }
  alphabet.erase(alphabet.begin() + ptr);
  str += first;
  for (int i = 1; i < n;) {
    if (((int) str.size() + 3) * 13 <= 4 * n) { /// floor(3^3 / 2) = 13
      std::vector<std::string> cand;
      for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
          for (int k = 0; k < 3; k++) {
            cand.push_back(alphabet[i] + alphabet[j] + alphabet[k]);
          }
        }
      }
      str += get(cand);
      i += 3;
    } else if (((int) str.size() + 2) * 4 <= 4 * n) { /// floor(3^3 / 2) = 4
      std::vector<std::string> cand;
      for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
          cand.push_back(alphabet[i] + alphabet[j]);
        }
      }
      str += get(cand);
      i += 2;
    } else {
      std::vector<std::string> cand;
      for (int i = 0; i < 3; i++) {
        cand.push_back(alphabet[i]);
      }
      str += get(cand);
      i++;
    }
  }
//  std::cout << "! " << str << '\n';
  return str;
}


#endif // COMBO_CPP_INCLUDED

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