Submission #1189235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189235		Zakir060	Combo (IOI18_combo)	C++20	30 / 100	10 ms	452 KiB

combo

#include <string>
#include <vector>
#include <numeric> // Not strictly needed but good practice for potential future use
#include <stdexcept> // For potential error handling if needed

// Forward declaration for the grader's function, assuming it's linked externally
// or provided in a header file (e.g., "combo.h")
// If using a specific contest environment, include the provided header.
// #include "combo.h"
extern int press(std::string p);

// Function to guess the secret sequence
std::string guess_sequence(int N) {
    std::string guessed_S = ""; // The string we are building
    char first_char = 0;       // To store the first character once found
    std::vector<char> all_chars = {'A', 'B', 'X', 'Y'};

    // --- Step 1: Determine the first character S[0] ---
    // We can determine the first character by pressing single characters.
    // If press("A") returns 1, the first character is 'A'.
    // Otherwise, try "B", then "X". If none return 1, it must be "Y".
    // This takes at most 3 calls to press().

    if (N == 0) {
        return ""; // Handle the edge case of N=0, though constraints likely guarantee N>=1
    }

    // Try A
    if (press("A") == 1) {
        guessed_S = "A";
    } else if (press("B") == 1) { // Try B if A failed
        guessed_S = "B";
    } else {                     // If A and B failed, try X
        // We can optimize slightly: if press("X") == 1, it's X.
        // If press("X") == 0, it must be Y. We don't need press("Y").
        if (press("X") == 1) {
            guessed_S = "X";
        } else {
            guessed_S = "Y";
        }
    }

    // Store the first character, knowing it won't repeat later.
    first_char = guessed_S[0];

    // If N is 1, we are already done.
    if (N == 1) {
        return guessed_S;
    }

    // --- Step 2: Determine the remaining characters S[1] to S[N-1] ---
    // We will determine the characters one by one.
    // Let the currently known prefix be `guessed_S`. Its length is `k`.
    // We want to find the next character `S[k]`.
    // We know `S[k]` cannot be `first_char`.
    // So, there are 3 possible candidates for `S[k]`. Let them be `c1, c2, c3`.

    // Optimized strategy:
    // Press `guessed_S + c1 + guessed_S + c2`.
    // - If result is `k`, it means neither `guessed_S + c1` nor `guessed_S + c2`
    //   is a prefix of S found in the pressed string. This implies the
    //   longest prefix found is still `guessed_S` (length k). Since we know the
    //   next character must be one of c1, c2, c3, and it's not c1 or c2,
    //   it *must* be c3. (1 press call)
    // - If result is `k+1`, it means *either* `guessed_S + c1` *or* `guessed_S + c2`
    //   is the correct next prefix S[0...k]. We need one more call to distinguish.
    //   Press `guessed_S + c1`.
    //     - If result is `k+1`, then `S[k]` is `c1`. (2 press calls total for this step)
    //     - If result is `k`, then `S[k]` must be `c2`. (2 press calls total for this step)
    // This determines each subsequent character in at most 2 calls.

    while (guessed_S.length() < N) {
        int k = guessed_S.length();
        char next_char = 0; // To store the determined next character

        // Identify the three candidate characters (all except first_char)
        std::vector<char> candidates;
        for (char c : all_chars) {
            if (c != first_char) {
                candidates.push_back(c);
            }
        }
        // `candidates` now holds the 3 possible next characters, let's call them c1, c2, c3.
        char c1 = candidates[0];
        char c2 = candidates[1];
        char c3 = candidates[2];

        // First query combining two candidates
        int r1 = press(guessed_S + c1 + guessed_S + c2);

        if (r1 == k) {
            // Neither c1 nor c2 worked when appended, so the next char must be c3
            next_char = c3;
        } else { // r1 == k + 1, meaning either c1 or c2 is the next character
            // Second query to distinguish between c1 and c2
            int r2 = press(guessed_S + c1);
            if (r2 == k + 1) {
                // Appending c1 resulted in the longer prefix match, so c1 is next
                next_char = c1;
            } else { // r2 == k
                // Appending c1 didn't extend the match, so c2 must be next
                next_char = c2;
            }
        }
        // Append the determined character to our result
        guessed_S += next_char;
    }

    // After the loop, guessed_S should have length N and be the correct sequence.
    return guessed_S;
}

// --- Explanation ---
//
// 1.  **Finding S[0]:** The first character is found by testing 'A', 'B', and 'X' individually using `press`. If `press(C)` returns 1, then `S[0]` is `C`. If none of 'A', 'B', 'X' return 1, `S[0]` must be 'Y'. This takes a maximum of 3 `press` calls.
// 2.  **Finding S[k] for k > 0:**
//     * We know `S[k]` cannot be `S[0]`. This leaves 3 possibilities.
//     * Let the current known prefix be `P = guessed_S` (length `k`).
//     * Let the 3 candidates be `c1`, `c2`, `c3`.
//     * We use a 2-stage query process:
//         * **Query 1:** `press(P + c1 + P + c2)`. This string contains potential prefixes `P+c1` and `P+c2`.
//         * **Analysis 1:**
//             * If `press` returns `k`: The longest prefix of `S` found is still `P`. This means neither `P+c1` nor `P+c2` is the *next* prefix `S[0...k]`. Therefore, the next character `S[k]` *must* be `c3`. We found `S[k]` in 1 call.
//             * If `press` returns `k+1`: The longest prefix found is length `k+1`. This means either `P+c1` or `P+c2` (or both, if they are identical which isn't possible here) matches `S[0...k]`. We need to know *which* one is correct.
//         * **Query 2 (only if Query 1 returned k+1):** `press(P + c1)`.
//         * **Analysis 2:**
//             * If `press` returns `k+1`: The prefix `P+c1` matches `S[0...k]`. So, `S[k]` is `c1`. We found `S[k]` in 2 calls total for this step.
//             * If `press` returns `k`: The prefix `P+c1` does *not* match `S[0...k]`. Since we knew from Query 1 that either `c1` or `c2` was correct, `S[k]` must be `c2`. We found `S[k]` in 2 calls total for this step.
// 3.  **Complexity:**
//     * Finding `S[0]` takes at most 3 calls.
//     * Finding each subsequent character `S[1]` to `S[N-1]` takes at most 2 calls.
//     * Total calls: Max `3 + 2 * (N - 1)`.
//     * For `N = 2000`, max calls = `3 + 2 * 1999 = 3 + 3998 = 4001`.
//     * This is well within the 8000 limit and should achieve the highest score tier (related to `2N + C` calls).
// 4.  **Constraints:** The pressed string length in `press(P + c1 + P + c2)` is `k + 1 + k + 1 = 2k + 2`. Since max `k` is `N-1`, the max length is `2(N-1) + 2 = 2N`. This is within the `4N` limit. The length in `press(P + c1)` is `k+1`, maximum `N`, also within limits.

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