Submission #1008555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008555		nickolasarapidis	Combo (IOI18_combo)	C++17	10 / 100	29 ms	1112 KiB

combo

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

string guess_sequence(int N){
	string S = "";
	int first = 5, last = 1;
	//bool a;

	char buttons[4] = {'A', 'B', 'X', 'Y'};
	vector<char> b; // size of b = 3

	for(int i = 0; i < 3; i++){
		if(press(S + buttons[i]) == 1){
			first = i;
			S += buttons[i];
			break;
		}
	}

	if(first == 5){
		first = 3;
		S += buttons[3];
	}

	// Q = 3 at worst

	for(int i = 0; i < 4; i++){
		if(i != first){
			b.push_back(buttons[i]); // New button list
		}
	}

	/*for(int i = 1; i < N; i++){
		a = false;
		for(int j = 0; j < 2; j++){
			if(press(S + b[j]) == i + 1){
				S += b[j];
				a = true;
				break;
			}
		}

		if(a == false){
			S += b[2];
		}
	}*/

	// Q = 2*N + 1 at worst (25 points)

	int prefix;

	for(int i = 1; i < N; i++){
		//a = false;

		prefix = press(S + b[0]);

		S += b[0];

		if(prefix == i + 1){
			last = i + 1;
		}
		else{
			last = prefix;
			if(S[last] == b[0]){
				S[last] = b[1];
			}
			else{
				S[last] = b[2];
			}
		}
	}

	prefix = press(S);

	while(prefix != N){
		last = prefix;
		if(S[last] == b[0]){
			S[last] = b[1];
		}
		else{
			S[last] = b[2];
		}

		prefix = press(S);
	}

	return S;
}

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