Submission #554102

#	Time	Username	Problem	Language	Result	Execution time	Memory
554102		d4xn	Combo (IOI18_combo)	C++17	30 / 100	38 ms	328 KiB

combo

#include "combo.h"

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

string guess_sequence(int N) {
  string p;

  for (char c : {'A', 'B', 'X'}) {
    p.pb(c);

    if (press(p)) {
      for (int i = 1; i < N; i++) {
        p.pb(c);
      }
      break;
    }

    p.pop_back();
  }

  if (p.empty()) {
    p.pb('Y');
    for (int i = 1; i < N; i++) {
      p.pb('Y');
    }
  }

  vector<char> v;
  for (char i : {'A', 'B', 'X', 'Y'}) {
    if (p[0] == i) continue;
    v.pb(i);
  }

  int idx = 1;
  while (idx < N) {

    for (int j = 0; j < 3; j++) {
      int k = j + rand() % (3 - j);
      swap(v[j], v[k]);
    }

    for (int i = idx+1; i - idx + 1 <= idx && i < N; i++) {
      p[i] = v[rand() % 3];
    }

    int temp = idx;
    
    for (int i = 0; i < 2; i++) {
      p[idx] = v[i];
      int x = press(p);
      if (x > idx) {
        idx = x;
        break;
      }
    }

    if (idx == temp) {
      p[idx] = v[2];
      idx = press(p);
    }
  }

  cerr << p << endl;
  return p;
}

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