Submission #107283

#	Time	Username	Problem	Language	Result	Execution time	Memory
107283		wonyoung	Combo (IOI18_combo)	C++14	100 / 100	50 ms	576 KiB

combo

#include <vector>
#include <string>
using namespace std;
int press(string p);

char binary_guess(string prefix, string cd)
{
    int pn = prefix.length();
    if (press(prefix + cd[0] + prefix + cd[1]) > pn)
    {
        if (press(prefix + cd[0]) > pn)
            return cd[0];
        return cd[1];
    }
    if (press(prefix + cd[2]) > pn)
        return cd[2];
    return cd[3];
}

string guess_sequence(int N)
{
    string prefix;
    string buttons = "ABXY";

    prefix += binary_guess("", buttons);
    buttons.erase(buttons.begin() + buttons.find(prefix[0]));

    if (N == 1)
        return prefix;

    int pn;
    while ((pn = prefix.length()) < N - 1)
    {
        string query_string;
        query_string += prefix + buttons[0];
        for (int i=0; i<3; i++)
            query_string += prefix + buttons[1] + buttons[i];
        int n = press(query_string);
        if (n == pn + 1)
            prefix += buttons[0];
        else if (n == pn + 2)
            prefix += buttons[1];
        else
            prefix += buttons[2];
    }
    prefix += binary_guess(prefix, buttons);

    return prefix;
}

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