Submission #916890

#	Time	Username	Problem	Language	Result	Execution time	Memory
916890		mpb_	Combo (IOI18_combo)	C++17	97 / 100	14 ms	1788 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"};
	auto guess = [&](string p) {
		return press(p);
	};
	if (N == 1) {
		for (int i = 0; i < 4; i++) {
			int coins = guess(ch[i]);
			if (coins == 1) {
				return ch[i];
			}
		}
	}
	auto find_fst = [&]() {
		string p = "AB";
		int coins = press(p);
		if (coins == 0) {
			p = "X";
			coins = press(p);
			return (coins == 1 ? "X" : "Y");
		} else {
			p = "A";
			coins = press(p);
			return (coins == 1 ? "A" : "B");
		}
	};
	string fst = find_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]);
	}
	string ans = fst;
	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 - 3; 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];
		}
	}
	for (int i = max(1, N - 2); i < N; i++) {
		bool found = false;
		for (int j = 0; j < 2; j++) {
			string tmp = ans + len1[j];
			int coins = guess(tmp);
			if (coins == i + 1) {
				found = true;
				ans += len1[j];
				break;
			}
		}
		if (!found) {
			ans += len1[2];
		}
	}
	return ans; 
}

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