Submission #1303867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303867		Cr45hor	Combo (IOI18_combo)	C++20	5 / 100	1 ms	336 KiB

combo

#include "combo.h"

std::string guess_sequence(int N) {
    std::string S = "";
    char buttons[] = {'A', 'B', 'X', 'Y'};
    if (N == 3) {
        S = "AAA";
        for (int i = 0; i < 64; i++) {
            int d1 = i % 4;
            int d2 = (i / 4) % 4;
            int d3 = (i / 16) % 4;
            S[0] = buttons[d1];
            S[1] = buttons[d2];
            S[2] = buttons[d3];
            if (press(S) == 3) {
                break;
            }
        }
        return S;
    }

    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]);
        }
    }

    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
    for (int i = 1; i <= 3; i++) {
        S = prefix + buttons[i];
        if (press(S) == N) {
            break;
        }
    }

    return S;
}

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