Submission #107282

#	Time	Username	Problem	Language	Result	Execution time	Memory
107282		wonyoung	Combo (IOI18_combo)	C++14	100 / 100	51 ms	596 KiB

combo

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

char binary_guess(string prefix)
{
    int pn = prefix.length();
    if (press(prefix + 'A' + prefix + 'B') > pn)
    {
        if (press(prefix + 'A') > pn)
            return 'A';
        return 'B';
    }
    if (press(prefix + 'X') > pn)
        return 'X';
    return 'Y';
}

string guess_sequence(int N)
{
    vector<char> buttons = { 'A', 'B', 'X', 'Y' };
    string prefix;

    prefix += binary_guess("");
  
  	if (N == 1)
      return prefix;
    for (vector<char>::iterator it = buttons.begin(); it != buttons.end(); it++)
        if (*it == prefix[0])
        {
            buttons.erase(it);
            break;
        }

    int i;
    bool skip = false;
    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);

    return prefix;
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:36:9: warning: unused variable 'i' [-Wunused-variable]
   36 |     int i;
      |         ^
combo.cpp:37:10: warning: unused variable 'skip' [-Wunused-variable]
   37 |     bool skip = false;
      |          ^~~~

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