Submission #277057

#	Time	Username	Problem	Language	Result	Execution time	Memory
277057		ASDF123	Combo (IOI18_combo)	C++14	94 / 100	41 ms	636 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 kek() {
//  int x = rnd();
//  return abs(x);
//}
//
//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 guess_sequence(int n) {
  string bad;
  string s;
  if (press("A") == 1) {
    s = "A";
  }
  else if (press("B") == 1) {
    s = "B";
  }
  else if (press("X") == 1) {
    s = "X";
  }
  else {
    s = "Y";
  }
  bad = s;

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

  for (int i = 1; i <= n - 2; i++) { // we guess i + 1 character
    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';
      }
    }
  }
  if (press(s + "A") == n) {
    s += "A";
  }
  else if (press(s + "B") == n) {
    s += "B";
  }
  else if (press(s + "X") == n) {
    s += "X";
  }
  else {
    s += "Y";
  }
  return s;
}


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

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