Submission #916897

#	Time	Username	Problem	Language	Result	Execution time	Memory
916897		mpb_	Combo (IOI18_combo)	C++17	100 / 100	13 ms	1968 KiB

combo

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

std::string guess_sequence(int N) {
	using namespace std;
	vector<string> ch = {"A", "B", "X", "Y"};
	int total = 0;
	auto guess = [&](string p) {
		total++;
		return press(p);
	};
	auto find_fst = [&]() {
		string p = "AB";
		int coins = guess(p);
		if (coins == 0) {
			p = "X";
			coins = guess(p);
			return (coins == 1 ? "X" : "Y");
		} else {
			p = "A";
			coins = guess(p);
			return (coins == 1 ? "A" : "B");
		}
	};
	string fst = find_fst();
	string ans = fst;
	vector<string> len1 = {};
	vector<string> len2 = {};
	for (auto c : ch) {
		if (c != fst) len1.push_back(c);
	}
	for (int i = 0; i < 3; i++) {
		len2.push_back(len1[1] + len1[i]);
	}
	auto build = [&]() {
		string tmp = ans;
		tmp += len1[0];
		for (auto x : len2) {
			tmp += (ans + x);
		}
		assert((int) tmp.size() <= 4 * N);
		return tmp;
	};
	for (int i = 1; i <= N - 2; i++) {
		string p = build();
		int coins = guess(p);
		if (coins == i) {
			ans += len1[2];
		} else if (coins == i + 1) {
			ans += len1[0];
		} else {
			ans += len1[1];
		}
	}
	if (N > 1) {
		bool found = false;
		for (int j = 0; j < 2; j++) {
			string tmp = ans + len1[j];
			int coins = guess(tmp);
			if (coins == N) {
				found = true;
				ans += len1[j];
				break;
			}
		}
		if (!found) {
			ans += len1[2];
		}
	}
	assert(total <= N + 2);
	return ans; 
}

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