Submission #277047

#	Time	Username	Problem	Language	Result	Execution time	Memory
277047		ASDF123	Combo (IOI18_combo)	C++14	94 / 100	44 ms	576 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
//#include <chrono>
//#include <random>
/*mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
string S;*/

//int press(string s) {
//  int mx = 0;
//  for (int i = 0; i < szof(s); i++) {
//    string sub = "";
//    for (int j = i; j < szof(s); j++) {
//      sub += s[j];
//      int pos = 0, siz = 0;
//      while (pos < sub.size() && sub[pos] == S[pos]) {
//        pos++, siz++;
//      }
//      mx = max(mx, siz);
//    }
//  }
//  return mx;
//}

string get(string pref) {
  if (press(pref + "A") == szof(pref) + 1) {
    return "A";
  }
  else if (press(pref + "B") == szof(pref) + 1) {
    return "B";
  }
  else if (press(pref + "X") == szof(pref) + 1) {
    return "X";
  }
  else {
    return "Y";
  }
}

string guess_sequence(int n) {
  string bad;
  string s = get("");
  bad = s;

  if (n == 1) {
    return s;
  }

  for (int i = 1; i <= n - 2; i++) { // we guess i + 1 character
    //cout << i << ": " << s << endl;
    int cost;
    if (bad == "A") {
      cost = press(s + "B" + s + "XY" + s + "XX" + s + "XB");
      if (cost == szof(s)) {
        s += 'Y';
      }
      if (cost == szof(s) + 1) {
        s += 'B';
      }
      if (cost == szof(s) + 2) {
        s += 'X';
      }
    }
    if (bad == "B") {
      cost = press(s + "A" + s + "XY" + s + "XX" + s + "XA");
      if (cost == szof(s)) {
        s += 'Y';
      }
      if (cost == szof(s) + 1) {
        s += 'A';
      }
      if (cost == szof(s) + 2) {
        s += 'X';
      }
    }
    if (bad == "X") { // { A B Y }
      cost = press(s + "A" + s + "BA" + s + "BB" + s + "BY");
      if (cost == szof(s)) {
        s += 'Y';
      }
      if (cost == szof(s) + 1) {
        s += 'A';
      }
      if (cost == szof(s) + 2) {
        s += 'B';
      }
    }
    if (bad == "Y") { // { A B X }
      cost = press(s + "A" + s + "BA" + s + "BB" + s + "BX");
      if (cost == szof(s)) {
        s += 'X';
      }
      if (cost == szof(s) + 1) {
        s += 'A';
      }
      if (cost == szof(s) + 2) {
        s += 'B';
      }
    }
  }
  s += get(s);
  return s;
}


//signed main() {
//  while (1) {
//    S.clear();
//    int n = rnd();
//    n %= 100;
//    S += 'A';
//    for (int i = 2; i <= n; i++) {
//      int x = rnd();
//      if (x % 3 == 0) {
//        S += 'B';
//      }
//      else if (x % 3 == 1) {
//        S += 'X';
//      }
//      else {
//        S += 'Y';
//      }
//    }
//    if (S != guess_sequence(n)) {
//      cout << S << " " << guess_sequence(n) << endl;
//      exit(0);
//    }
//  }
//}

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