Submission #425423

#	Time	Username	Problem	Language	Result	Execution time	Memory
425423		KoD	Combo (IOI18_combo)	C++17	100 / 100	51 ms	716 KiB

combo

#include <bits/stdc++.h>
#include "combo.h"

template <class T> using Vec = std::vector<T>;
constexpr char LET[] = {'A', 'B', 'X', 'Y'};

std::string guess_sequence(int N) {
    std::string cur;
    cur.push_back([&] {
        if (press("AB") == 0) {
            return press("X") ? 'X' : 'Y';
        } else {
            return press("A") ? 'A' : 'B';
        }
    }());
    if (N == 1) {
        return cur;
    }
    Vec<int> other;
    for (int i = 0; i < 4; ++i) {
        if (LET[i] != cur[0]) {
            other.push_back(i);
        }
    }
    for (int i = 1; i < N - 1; ++i) {
        std::string ask;
        for (int k = 0; k < 3; ++k) {
            ask += cur;
            ask += LET[other[0]];
            ask += LET[other[k]];
        }
        ask += cur;
        ask += LET[other[1]];
        cur += LET[other[2 - (press(ask) - i)]];
    }
    for (int k = 0; k < 2; ++k) {
        std::string tmp = cur + LET[other[k]];
        if (press(tmp) == N) {
            return tmp;
        }
    }
    return cur + LET[other[2]];
}

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