Submission #785905

#	Time	Username	Problem	Language	Result	Execution time	Memory
785905		Boas	Combo (IOI18_combo)	C++17	30 / 100	87 ms	924 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
using namespace std;

string guess_sequence(int N)
{
    vector<char> buttons = {'A', 'B', 'X', 'Y'};
    string S;
    for (int i = 0; i < 3; i++)
    {
        string p = S + buttons[i];
        if (press(p) == 1)
        {
            S = p;
            buttons.erase(find(ALL(buttons), buttons[i]));
            break;
        }
    }
    if (S.size() == 0)
        S += 'Y';

    while (S.size() < N)
    {
        vector<string> all = {S};
        while (((all.size() * 3 + 1) / 2) * (all[0].size() + 1) + 1 <= 4 * N)
        {
            cerr << ((all.size() * 3) * (all[0].size() + 1) + 1) / 2 << "<=" << 4 * N << endl;
            int s = all.size();
            for (int i = 0; i < s; i++)
            {
                all.push_back(all[i] + buttons[1]);
                all.push_back(all[i] + buttons[2]);
                all[i] += buttons[0];
            }
            if (all[0].size() == N)
                break;
        }
        int min = 0;
        int max = all.size() - 1;
        while (max != min)
        {
            int k = (max + min) / 2;
            string p;
            for (int i = min; i <= k; i++)
            {
                p += all[i];
            }
            cerr << "p.size() = " << p.size() << " en 4N = " << 4 * N << endl;
            // resterende ruimte opvullen met random junk
            int res = press(p);
            // if( S.size() < res < all[0].size()) { filter all op mogelijkheden!;}
            if (res == all[0].size())
            {
                max = k;
            }
            else
            {
                min = k + 1;
            }
        }
        S = all[min];
        // cerr << "Done?!" << endl;
    }
    return S;
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:23:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     while (S.size() < N)
      |            ~~~~~~~~~^~~
combo.cpp:26:69: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         while (((all.size() * 3 + 1) / 2) * (all[0].size() + 1) + 1 <= 4 * N)
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
combo.cpp:36:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |             if (all[0].size() == N)
      |                 ~~~~~~~~~~~~~~^~~~
combo.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (res == all[0].size())
      |                 ~~~~^~~~~~~~~~~~~~~~

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