Submission #1057456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057456		xnqs	Combo (IOI18_combo)	C++17	100 / 100	17 ms	1444 KiB

combo

#include "combo.h"

char binary_search(const std::string& str) {
	if (press(str+"A"+str+"B")==str.size()) {
		return ((press(str+"X")==str.size()) ? 'Y' : 'X');
	}
	else {
		return ((press(str+"A")==str.size()) ? 'B' : 'A');
	}
}

char get_next(const std::string& str) {
	const char* const buttons = "ABXY";

	char pressable[3] = {0};
	for (int i = 0; i < 4; i++) {
		if (str[0]==buttons[i]) {
			int ptr = 0;
			for (int j = 0; j < 4; j++) {
				if (j!=i) {
					pressable[ptr++] = buttons[j];
				}
			}
		}
	}

	std::string combo_1; combo_1 += pressable[0];
	std::string combo_2; combo_2 += pressable[1]; combo_2 += pressable[0];
	std::string combo_3; combo_3 += pressable[1]; combo_3 += pressable[1];
	std::string combo_4; combo_4 += pressable[1]; combo_4 += pressable[2];

	std::string tmp = str + combo_1 + str + combo_2 + str + combo_3 + str + combo_4;
	//printf("%s %s\n",str.c_str(),tmp.c_str());
	int longest_pfx = press(tmp);
	if (longest_pfx==str.size()) {
		return pressable[2];
	}
	else if (longest_pfx==str.size()+1) {
		return pressable[0];
	}
	else {
		return pressable[1];
	}
}

std::string guess_sequence(int N) {
	std::string ret;
	ret += binary_search(ret);

	while (ret.size()+2<=N) {
		ret += get_next(ret);
	}

	while (ret.size()+1<=N) {
		ret += binary_search(ret);
	}
	return ret;
}

Compilation message (stderr)

combo.cpp: In function 'char binary_search(const string&)':
combo.cpp:4:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |  if (press(str+"A"+str+"B")==str.size()) {
      |      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
combo.cpp:5:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 |   return ((press(str+"X")==str.size()) ? 'Y' : 'X');
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~~
combo.cpp:8:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |   return ((press(str+"A")==str.size()) ? 'B' : 'A');
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~~
combo.cpp: In function 'char get_next(const string&)':
combo.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  if (longest_pfx==str.size()) {
      |      ~~~~~~~~~~~^~~~~~~~~~~~
combo.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  else if (longest_pfx==str.size()+1) {
      |           ~~~~~~~~~~~^~~~~~~~~~~~~~
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:50:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |  while (ret.size()+2<=N) {
      |         ~~~~~~~~~~~~^~~
combo.cpp:54:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |  while (ret.size()+1<=N) {
      |         ~~~~~~~~~~~~^~~

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