Submission #107287

#	Time	Username	Problem	Language	Result	Execution time	Memory
107287		wonyoung	Combo (IOI18_combo)	C++14	100 / 100	44 ms	628 KiB

combo

#include "combo.h"
using namespace std;

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

    if (btn.length() > 3 && press(prefix + btn[3]) > pn)
        return btn[3];

    return btn[2];
}

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

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

    if (N == 1)
        return prefix;

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

    return prefix;
}

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