Submission #837985

#	Time	Username	Problem	Language	Result	Execution time	Memory
837985		iee	Combo (IOI18_combo)	C++17	100 / 100	47 ms	688 KiB

combo

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

using V = basic_string<int>;

string Dict = "ABXY", orig;

int get(V v) {
	string s;
	for (int x : v) {
		if (x == -1) {
			s += orig;
		} else {
			s += Dict[x];
		}
	}
	return press(s);
}

std::string guess_sequence(int N) {
	vector<int> ans(N);
	ans[0] = (get({0, 1}) ? get({0}) ? 0 : 1 : get({2}) ? 2 : 3);
	orig = string(1, Dict[ans[0]]);
	if (N == 1) {
		return orig;
	}
	Dict.erase(Dict.begin() + ans[0]);
	for (int i = 1; i < N - 1; i++) {
		V k{-1};
		for (int j = 1; j < i; j++) {
			k += ans[j];
		}
		int t = get(k + 0 + 0 + k + 0 + 1 + k + 0 + 2 + k + 1);
		ans[i] = (t == i ? 2 : t == i + 1 ? 1 : 0);
	}
	V k{-1};
	for (int j = 1; j < N - 1; j++) {
		k += ans[j];
	}
	ans[N - 1] = (get(k + 0 + k + 1) == N ? get(k + 0) == N ? 0 : 1 : 2);
	string S;
	S.resize(N);
	S[0] = "ABXY"[ans[0]];
	for (int i = 1; i < N; i++) {
		S[i] = Dict[ans[i]];
	}
	return S;
}

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