Submission #554180

#	Time	Username	Problem	Language	Result	Execution time	Memory
554180		d4xn	Combo (IOI18_combo)	C++17	30 / 100	24 ms	300 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;

  vector<char> f = {'A', 'B', 'X', 'Y'};

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

  int idx = 0;
  for (int i = 0; i < 3; i++) {
    p.pb(f[i]);

/*
    for (int j = 1; j < N; j++) {
      char x = f[rand() % 4];
      while (x == f[i]) {
        x = f[rand() % 4];
      }
      p.pb(x);
    }
*/

    idx = press(p);
    if (idx) break;

    p.clear();
  }

  if (!idx) {
    p.pb(f[3]);
  }

  for (int i = 1; i < N; i++) {
    char x = f[rand() % 4];
    while (x == p[0]) {
      x = f[rand() % 4];
    }
    p.pb(x);
  }

  idx = press(p);

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

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

  while (idx < N) {
    char x, y;
    x = y = 'a';
    for (int i = 0; i < 3; i++) {
      if (p[idx] == v[i]) continue;
      if (x == 'a') x = v[i];
      else y = v[i];
    }

    p[idx] = x;
    int newIdx = press(p);

    if (newIdx > idx) {
      idx = newIdx;
    }
    else {
      p[idx] = y;
      idx = press(p);
    }
  }

  return p;
}

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