Submission #393818

#	Time	Username	Problem	Language	Result	Execution time	Memory
393818		ruadhan	Combo (IOI18_combo)	C++17	100 / 100	42 ms	544 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()

// string S;
// int N;
// int calls = 0;

// int press(string p)
// {
//     calls++;
//     // cout << "pressing " << p << '\n';
//     if ((int)p.length() > N * 4)
//         return -1;
//     int ret = 0;
//     int counter = 0;
//     int i = 0;
//     int j = 0;
//     while (i < (int)p.size())
//     {
//         // cout << "i = " << i << '\n';
//         while (i < (int)p.size() && j < (int)S.size() && p.at(i) == S.at(j))
//         {
//             i++, j++, counter++;
//         }
//         ret = max(ret, counter);
//         j = 0, i++;
//         counter = 0;
//     }
//     return ret;
// }

string guess_sequence(int N)
{
    string s;
    s.reserve(N);

    vector<char> ch = {'A', 'B', 'X', 'Y'};

    if (press("AB"))
        s += (press("A") ? "A" : "B");
    else
        s += (press("X") ? "X" : "Y");

    ch.erase(find(ch.begin(), ch.end(), s[0]));

    if (N == 1)
        return s;

    for (int i = 1; i < N - 1; i++)
    {
        string combo = s + ch[0] + s + ch[1] + ch[0] + s + ch[1] + ch[1] + s + ch[1] + ch[2];
        int curr_sz = sz(s);
        int qry = press(combo);
        // int qry = press(s + ch[0] + s + ch[1] + ch[1]);
        if (curr_sz + 2 == qry)
            s += ch[1];
        else if (curr_sz + 1 == qry)
            s += ch[0];
        else
            s += ch[2];
    }
    if (sz(s) == N)
        return s;
    if (press(s + "A" + s + "B") > sz(s))
        s += (press(s + "A") > sz(s) ? "A" : "B");
    else
        s += (press(s + "X") > sz(s) ? "X" : "Y");
    return s;
}

// int main()
// {
//     S = "ABYXBYXBB";
//     N = S.length();

//     cout << guess_sequence(N) << '\n';
//     cerr << "Function Calls = " << calls << '\n';
//     return 0;
// }

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