Submission #1186836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186836		astoria	Combo (IOI18_combo)	C++20	0 / 100	0 ms	396 KiB

combo

#include "combo.h"
#include <string>
using namespace std;

string guess_sequence(int N)
{
    /* ----------  Step 1 : find S0 in exactly two queries  ---------- */
    auto press_once = [&](const string& p){ return press(p); };

    char S0;
    if (press_once("AB") == 1)        // A or B ?
        S0 = (press_once("A") == 1) ? 'A' : 'B';
    else                              // X or Y
        S0 = (press_once("X") == 1) ? 'X' : 'Y';

    string pref(1, S0);

    /* remaining three letters in some fixed order */
    string rest = "ABXY";
    rest.erase(rest.find(S0), 1);     // remove S0
    char P = rest[0], Q = rest[1], R = rest[2];

    /* ----------  Step 2 : solve two characters with ≤ 2 presses  ---------- */
    while ((int)pref.size() < N)
    {
        int k = (int)pref.size();
        /* first query of the block */
        string q1 = pref + P + Q + pref + P;
        int r1 = press_once(q1);

        if (r1 == k + 2) {                 // we got both letters P Q
            pref.push_back(P);
            if ((int)pref.size() < N) pref.push_back(Q);
            continue;                      // use next loop iteration as “second query”
        }

        if (r1 == k + 1) {                 // next letter is P
            pref.push_back(P);
        } else {                           // r1 == k  → next letter is R
            pref.push_back(R);
        }
        if ((int)pref.size() == N) break;  // solved the last character

        /* exactly one more query to learn the following letter */
        int k2 = (int)pref.size();
        string q2 = pref + Q + pref;       // test Q
        int r2 = press_once(q2);
        pref.push_back( (r2 == k2 + 1) ? Q : R );
    }
    return pref;
}

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