제출 #1189239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189239		Zakir060	콤보 (IOI18_combo)	C++20	30 / 100	12 ms	452 KiB

combo

#include <string>
#include <vector>
#include <numeric>
#include <algorithm> // Required for std::find

// Forward declaration or include header
// #include "combo.h"
extern int press(std::string p);

std::string guess_sequence(int N) {
    std::string guessed_S = "";
    std::vector<char> all_chars = {'A', 'B', 'X', 'Y'};
    char first_char = 0;

    if (N == 0) {
        return "";
    }

    // --- Step 1: Determine the first character S[0] ---
    if (press("A") == 1) {
        guessed_S = "A";
    } else if (press("B") == 1) {
        guessed_S = "B";
    } else {
        if (press("X") == 1) {
            guessed_S = "X";
        } else {
            guessed_S = "Y";
        }
    }
    first_char = guessed_S[0];

    // --- Step 2: Determine the remaining characters S[1] to S[N-1] ---
    while (guessed_S.length() < N) {
        int k = guessed_S.length();
        char next_char = 0;

        // Identify candidates: c1, c2, c3 != first_char; c4 = first_char
        std::vector<char> other_chars;
        for (char c : all_chars) {
            if (c != first_char) {
                other_chars.push_back(c);
            }
        }
        char c1 = other_chars[0];
        char c2 = other_chars[1];
        char c3 = other_chars[2];
        char c4 = first_char; // Candidate 4 is the first char

        // Query 1: Test pair (c1, c2)
        int r1 = press(guessed_S + c1 + guessed_S + c2);

        if (r1 == k + 1) {
            // Case A: Possibilities are c1 or c2
            // Query 2: Distinguish c1 / c2
            int r2 = press(guessed_S + c1);
            if (r2 == k + 1) {
                next_char = c1;
            } else { // r2 must be k
                next_char = c2;
            }
        } else { // r1 == k
            // Case B: Possibilities are c3 or c4
            // Query 2: Distinguish c3 / c4
            int r3 = press(guessed_S + c3);
            if (r3 == k + 1) {
                next_char = c3;
            } else { // r3 must be k
                next_char = c4; // The first character reappears
            }
        }

        // Append the determined character
        guessed_S.push_back(next_char);
    }

    return guessed_S;
}

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