Submission #1205844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205844		kitkat12	Combo (IOI18_combo)	C++20	0 / 100	6 ms	508 KiB

combo

// Problem URL: https://oj.uz/problem/view/IOI18_combo
// Start Time: 5/22/2025, 1:37:39 PM

#include <bits/stdc++.h>
#include "combo.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int i = a; i < b; i++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)

string guess_sequence(int n)
{
    vector<char> abc = {'A','B','X','Y'};

    /* ---- 1. find the first letter ---- */
    int r = press("AB");          // 0, 1 or 2
    char first;
    if (r) {                      // it's A or B
        first = press("A") ? 'A' : 'B';
    } else {                      // it's X or Y
        first = press("X") ? 'X' : 'Y';
    }
    string pref(1, first);

    /* keep the three letters that can still appear */
    vector<char> rest;
    for (char c : abc) if (c != first) rest.push_back(c);

    const char p = rest[0];   // old “A”
    const char q = rest[1];   // sentinel, old “Y”
    const char r_ = rest[2];  // old “B”

    /* ---- 2. build positions 2 … n-1 ---- */
    for (int i = 1; i < n - 1; ++i) {
        string qstr;
        qstr.reserve((i + 1) * 4 + 3);        // small perf tweak

        qstr += pref; qstr.push_back(p);
        qstr += pref; qstr.push_back(q); qstr.push_back(q);
        qstr += pref; qstr.push_back(q); qstr.push_back(p);
        qstr += pref; qstr.push_back(q); qstr.push_back(r_);

        int k = press(qstr);
        if (k == pref.size() + 1)      pref.push_back(p);
        else if (k == pref.size() + 2) pref.push_back(r_);
        else                           pref.push_back(q);
    }
    if (n == 1) return pref;           // nothing else to do

    /* ---- 3. resolve the very last character ---- */
    string try1 = pref + q + pref + p;   // ...q...p
    int k = press(try1);

    if (k == n - 1) {                    // mismatch at last char
        pref.push_back(r_);
    } else {                             // could be q or p
        pref.push_back(press(pref + q) == n ? q : p);
    }
    return pref;
}

// string guess_sequence(int n){
//     string pref = "X";
//     // guess first letter
//     int res = press("XY");
//     switch (res)
//     {
//     case 1:
//         res = press("XA");
//         if(!res) pref = "Y";
//         break;
//     case 0:
//         pref="A";
//         res = press("AX");
//         if(!res) pref = "B";
//         break;
//     default:
//         break;
//     }

//     li(i,1,n-1){
//         stringstream q;
//         q << pref << "A" << pref << "YY" << pref <<"YA"<<pref<<"YB";
//         res = press(q.str());
//         if(res==i+1){
//             pref.append("B");
//         }
//         else if(res == i+2){
//             pref.append("A");
//         }
//         else{
//             pref.append("Y");
//         }
//     }

//     stringstream q;
//     q << pref <<"Y"<<pref<<"A";
//     res = press(q.str());

//     if(res==n-1){
//         pref.append("B");
//     }
//     else{
//         q.clear();
//         q << pref <<"Y";
//         res = press(q.str());
//         if(res == n){
//             pref.append("Y");
//         }
//         else{
//             pref.append("A");
//         }
//     }
//     return pref;
// }

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