Submission #884468

#	Time	Username	Problem	Language	Result	Execution time	Memory
884468		gustavo_d	Combo (IOI18_combo)	C++17	100 / 100	14 ms	1792 KiB

combo

// https://oj.uz/problem/view/IOI18_combo > p152
#include "combo.h"
#include <bits/stdc++.h>
using namespace std;

/*
botões A,B,X,Y no jogo, você pode fazer combos apertando + de um juntos
tem uma sequência secreta S de N chars
primeiro char dela nunca repete, bruta A, B, C, D (AABB, CCDD > o que for, você tenta um e se n é o outro; custo 3) > sobra 3 possibilidades pro resto; sendo A, ABAC se n for é o AD, se não tenta tipo AB se nao for é o AC (custo 2n-2)
você deve digitar até 4N chars, sua pontuação é o tamanho do maior prefixo de S que é substring da sequência sua
após o mínimo de combos 4N, você deve descobrir S

custo total: 2n-2+2 = 2n

pode chamar press com 0 a 4N chars até 8000 vezes e N até 2000

q<=N+2

O(n)
primeira: 4 chamadas, testa primeiro char
2N: só sobra 3 possibilidades pra cada char (primeiro não repete), aí vocẽ testa primeiro com segundo se for, testa 1 se não for é o outro; se não é os 2, é o 3o
*/

string guess_sequence(int N) {
  string S = "";
  string p = "AB";
  int coins = press(p);
  if (coins == 0) { // ou X out Y
	  p = "X";
	  coins = press(p);
	  if (coins == 0) S = "Y";
	  else S = "X";
  } else {
	  p = "A";
	  coins = press(p);
	  if (coins == 0) S = "B";
	  else S = "A";
  }
  vector<char> others;
  if ('A' != S[0]) others.push_back('A');
  if ('B' != S[0]) others.push_back('B');
  if ('X' != S[0]) others.push_back('X');
  if ('Y' != S[0]) others.push_back('Y');
  for (int i = 0; i < N-1; i++) {
	  p = "" + S;
	  p += others[0];
	  p += S;
	  p += others[1];
	  if (i < N-2) {
		  p += others[0];
		  p += S; p += others[1]; p += others[1];
		  p += S; p += others[1]; p += others[2];
		  coins = press(p);
		  if (coins == (int)S.size() + 1) S += others[0];
		  else if (coins == (int)S.size() + 2) S += others[1];
		  else S += others[2];
	  } else {
		  coins = press(p);
		  if (coins == (int)S.size()) S += others[2]; // sem query extra descobre
		  else { // precisa já na primeira descobrir se é o primeiro ou o segundo char (se der no segundo char coloca a combinação dos 3 chars depois além dele) >> 4N dá sempre
			  p = "" + S;
			  p += others[0];
			  coins = press(p);
			  if (coins == (int)S.size()) S += others[1];
			  else S += others[0];
		  }
	  }
  }
  return S;
}

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