Submission #1007462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007462		makanhulia	Combo (IOI18_combo)	C++17	100 / 100	18 ms	1944 KiB

combo

#include<bits/stdc++.h>
#include "combo.h"
#define str string

using namespace std;

// note that we don't have to press a string of length exactly 4N, instead 4N is the maximum length of the pressed string

set<char> C;
char c[3];

str guess_sequence(int N) {
  str p = "";
  
  C.insert('A');
  C.insert('B');
  C.insert('X');
  C.insert('Y');
  
  // firstly, there are 4 options for the first character (A, B, X,  Y)
  // the most optimal way to get the first character is to press "AB" 
  // if we get coins >= 1, then the first character is 'A' or 'B'
  // similarly the first character is 'X' or 'Y' if we get 0 coins
  int Q1 = press("AB"), Q2;
  if (Q1 > 0) {
    Q2 = press("A");
    if (Q2 > 0) {
      p += 'A';
      C.erase('A');
    }
    else {
      p += 'B';
      C.erase('B');
    }
  }
  else {
    Q2 = press("X");
    if (Q2 > 0) {
      p += 'X';
      C.erase('X');
    }
    else {
      p += 'Y';
      C.erase('Y');
    }
  }
  
  if (N == 1) {
    return p;
  }
  
  // NOTE that the first character will not appear again later in S
  // for the next n-2 characters we use the following format as a strategy
  // let P be the already known/fixed prefix
  // p = PXXPXAPXBPA
  // p = PC[0]C[0]PC[0]C[1]PC[0]C[2]PC[1]
  
  char c[3];
  int idx = 0;
  for (char j: C) {
    c[idx] = j;
    idx++;
  }  
  
  for (int i=1; i<=N-2; i++) {
    int Qmid = press(p+c[0]+c[0]+p+c[0]+c[1]+p+c[0]+c[2]+p+c[1]);
    if (Qmid == i) {
      // then the next char is c[2]
      p += c[2];
      continue;
    }
    else if (Qmid == i+1) {
      // ... next char is c[1]
      p += c[1];
      continue;
    }
    else {
      // ... next char is c[0]
      p += c[0];
      continue;
    }
    
  }
  
  // so far we've pressed 2 + n-2 = n times
  // 2 presses left
  
  int Qlast1 = press(p+c[0]);
  int Qlast2 = press(p+c[1]);
  if (Qlast1 == N) p += c[0];
  else if (Qlast2 == N) p += c[1];
  else p += c[2]; 
  str S = "";
  for (int i = 0; i < N; ++i) {
      S += p[i];
  }
  return S;
}

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