Submission #551956

#	Time	Username	Problem	Language	Result	Execution time	Memory
551956		TranGiaHuy1508	Combo (IOI18_combo)	C++17	100 / 100	35 ms	584 KiB

combo

#include <bits/stdc++.h>
using namespace std;

string charset = "ABXY";
int root;
vector<int> others;
string prefix;

int press(string p);

string guess_sequence(int N){
	// Find "root"
	{
		int res1 = press("AB");
		if (res1 > 0){
			int res2 = press("A");
			if (res2 > 0) root = 0;
			else root = 1;
		}
		else{
			int res2 = press("X");
			if (res2 > 0) root = 2;
			else root = 3;
		}
	}

	others.clear();

	// Init
	for (int i = 0; i < 4; i++){
		if (i != root) others.push_back(i);
	}

	string s0 = string(1, charset[others[0]]), s1 = string(1, charset[others[1]]),
	s2 = string(1, charset[others[2]]), sr = string(1, charset[root]);


	// Find N-2 middle characters
	prefix = charset[root];
	for (int i = 1; i < N-1; i++){
		vector<string> added;
		
		added.push_back(s0 + s0);
		added.push_back(s0 + s1);
		added.push_back(s0 + s2);
		added.push_back(s1 + sr);

		string query = "";
		for (auto s: added) query += prefix + s;

		int r = press(query);
		if (r == i+2) prefix += s0;
		else if (r == i+1) prefix += s1;
		else prefix += s2;
	}

	if (N >= 2){
		int res1 = press(prefix + s0);
		if (res1 == N) prefix += s0;
		else{
			int res2 = press(prefix + s1);
			if (res2 == N) prefix += s1;
			else prefix += s2;
		}
	}

	return prefix;
}

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