Submission #1303877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303877		Cr45hor	Combo (IOI18_combo)	C++17	100 / 100	9 ms	464 KiB

combo

#include "combo.h"
#include "assert.h"

std::string guess_sequence(int N) {
    std::string S = "";
    char buttons[] = {'A', 'B', 'X', 'Y'};

    std::string p = "";
    char first_character;
    // guess the first character
    p = "AB";
    if (press(p) > 0) {
        p = "A";
        if (press(p) > 0) {
            first_character = 'A';
        }
        else {
            first_character = 'B';
            std::swap(buttons[0], buttons[1]);
        }
    }
    else {
        p = "X";
        if (press(p) > 0) {
            first_character = 'X';
            std::swap(buttons[0], buttons[2]);
        }
        else {
            first_character = 'Y';
            std::swap(buttons[0], buttons[3]);
        }
    }
    if (N == 1) {
        return std::string(1, first_character);
    }

    std::string prefix(1, first_character);
    for (int i = 2; i <= N - 1; i++) {
        std::string query = prefix + buttons[1] + buttons[1] + prefix + buttons[1] + buttons[2] + prefix + buttons[1] + buttons[3] + prefix + buttons[2];
        int curr_coin = press(query);
        if (curr_coin == i + 1) {
            prefix += buttons[1];
        }
        else if (curr_coin == i) {
            prefix += buttons[2];
        }
        else {
            prefix += buttons[3];
        }
    }

    // guess the last character
    bool found = false;
    for (int i = 1; i <= 2; i++) {
        S = prefix + buttons[i];
        if (press(S) == N) {
            found = true;
            break;
        }
    }
    if (!found) {
        S = prefix + buttons[3];
    }

    return S;
}

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