Submission #1018099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018099		pawned	Combo (IOI18_combo)	C++17	100 / 100	23 ms	2296 KiB

combo

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "combo.h"

map<char, int> conv = {{'A', 0}, {'B', 1}, {'X', 2}, {'Y', 3}};
char convr[4] = {'A', 'B', 'X', 'Y'};

char firstLetter() {	// finds first letter
	int res = press("AB");
	if (res >= 1) {
		int res2 = press("A");
		if (res2 == 1)
			return 'A';
		else
			return 'B';
	}
	else {
		int res2 = press("X");
		if (res2 == 1)
			return 'X';
		else
			return 'Y';
	}
}

char nextLetter(string s) {	// finds next letter
//	cout<<"at "<<s<<endl;
	int K = s.size();
	char fs = s[0];	// first character
	vector<char> opt;	// posssible next letters
	for (int i = 0; i < 4; i++) {
		if (convr[i] != fs)
			opt.pb(convr[i]);
	}
	vector<string> nx;
	// ends with opt[0]
	for (int i = 0; i < 3; i++) {
		nx.pb(s + opt[0] + opt[i]);
	}
	// ends with opt[1]
	nx.pb(s + opt[1]);
	// ends with opt[2]
/*	cout<<"nx: ";
	for (string st : nx)
		cout<<st<<" ";
	cout<<endl;*/
	string tq;	// to query
	for (int i = 0; i < 4; i++) {
		tq += nx[i];
	}
	int res = press(tq);
//	cout<<"res: "<<res<<endl;
	if (res == K + 2)
		return opt[0];
	else if (res == K + 1)
		return opt[1];
	return opt[2];
}

char lastLetter(string s) {
	int K = s.size();
	char fs = s[0];	// first character
	vector<char> opt;	// posssible next letters
	for (int i = 0; i < 4; i++) {
		if (convr[i] != fs)
			opt.pb(convr[i]);
	}
	int r1 = press(s + opt[0]);
	int r2 = press(s + opt[1]);
	if (r1 == K + 1)
		return opt[0];
	if (r2 == K + 1)
		return opt[1];
	return opt[2];
}

string guess_sequence(int N) {
	string s;
	char c = firstLetter();
	s += c;
	for (int i = 1; i < N - 1; i++) {	// guess ith letter
		char cp = nextLetter(s);
		s += cp;
	}
	if (N != 1) {
		char cn = lastLetter(s);
		s += cn;
	}
//	cout<<"found "<<s<<endl;
	return s;
}

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