Submission #115940

#	Time	Username	Problem	Language	Result	Execution time	Memory
115940		user202729	Combo (IOI18_combo)	C++17	100 / 100	41 ms	660 KiB

combo

#include "combo.h"

#include<string>
#include<array>

std::string guess_sequence(int N) {
	std::string pre; // constructed prefix so far

	{
		std::string an(N,'A');
		std::string bn(N,'B');

		if(press(an+bn)>0){
			if(press(an)>0)
				pre="A";
			else
				pre="B";
		}else{
			std::string xn(N,'X');
			if(press(xn)>0)
				pre="X";
			else
				pre="Y";
		}
	}

	if(N==1)return pre;

	char a,b,c; // the 3 nonfirst chars
	{
		std::array<char,4> nonfirst_chars{{'A','B','X','Y'}};
		auto iter=nonfirst_chars.begin();
		while(pre[0]!=*iter)
			++iter;
		std::swap(*iter,nonfirst_chars[0]);
		a=nonfirst_chars[1];
		b=nonfirst_chars[2];
		c=nonfirst_chars[3];
	}

	while((int)pre.size()<N-1){
		switch(press(pre+a+a+pre+a+b+pre+a+c+pre+b)-pre.size()){
			case 0:pre+=c;break;
			case 1:pre+=b;break;
			case 2:pre+=a;break;
			default:__builtin_trap();
		}
	}

	std::string tmp=pre+a;
	if(press(tmp)==N)return tmp;
	tmp=pre+b;
	if(press(tmp)==N)return tmp;
	return pre+c;
}

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