Submission #790382

#	Time	Username	Problem	Language	Result	Execution time	Memory
790382		Boas	Combo (IOI18_combo)	C++17	30 / 100	141 ms	1204 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';
    vector<string> all = {S};
    while (S.size() < N)
    {
        int newTotal = all.size() * 3;
        int halfTotal = (newTotal + 1) / 2;
        int newSize = all[0].size() + 1;
        while (halfTotal * newSize <= 4 * N)
        {
            cerr << "newTotal: " << newTotal << endl;
            cerr << "halfTotal: " << halfTotal << endl;
            cerr << "newSize: " << newSize << endl;
            if (all[0].size() + 1 > N)
                break;
            cerr << halfTotal * newSize << " < " << 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;

            newTotal = all.size() * 3;
            halfTotal = (newTotal + 1) / 2;
            newSize = all[0].size() + 1;
        }
        int k = (all.size() + 1) / 2;
        string p;
        for (int i = 0; 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 (res == all[0].size())
        {
            all.erase(all.begin() + k, all.end());
        }
        else
        {
            if (res > S.size())
            {
                string common = all[0];
                for (int i = 1; i < all.size(); i++)
                {
                    for (int ix = 0; ix < std::min(common.size(), all[i].size()); ix++)
                    {
                        if (common[ix] != all[i][ix])
                        {
                            common.erase(common.begin() + ix, common.end());
                            break;
                        }
                    }
                }
                all.erase(all.begin(), all.begin() + k);
                for (int i = 0; i < all.size(); i++)
                {
                    for (int ix = 0; ix < std::min(common.size(), all[i].size()); ix++)
                    {
                        if (common[ix] != all[i][ix])
                        {
                            all.erase(all.begin() + i);
                            i--;
                            break;
                        }
                    }
                }
            }
            else
                all.erase(all.begin(), all.begin() + k);
        }
        S = all[0];
        for (int i = 1; i < all.size(); i++)
        {
            for (int ix = 0; ix < std::min(S.size(), all[i].size()); ix++)
            {
                if (S[ix] != all[i][ix])
                {
                    S.erase(S.begin() + ix, S.end());
                    break;
                }
            }
        }
        // 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:33:35: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |             if (all[0].size() + 1 > N)
      |                 ~~~~~~~~~~~~~~~~~~^~~
combo.cpp:43:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |             if (all[0].size() == N)
      |                 ~~~~~~~~~~~~~~^~~~
combo.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         if (res == all[0].size())
      |             ~~~~^~~~~~~~~~~~~~~~
combo.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if (res > S.size())
      |                 ~~~~^~~~~~~~~~
combo.cpp:68:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for (int i = 1; i < all.size(); i++)
      |                                 ~~^~~~~~~~~~~~
combo.cpp:70:41: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   70 |                     for (int ix = 0; ix < std::min(common.size(), all[i].size()); ix++)
      |                                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
combo.cpp:80:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 for (int i = 0; i < all.size(); i++)
      |                                 ~~^~~~~~~~~~~~
combo.cpp:82:41: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   82 |                     for (int ix = 0; ix < std::min(common.size(), all[i].size()); ix++)
      |                                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
combo.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int i = 1; i < all.size(); i++)
      |                         ~~^~~~~~~~~~~~
combo.cpp:99:33: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   99 |             for (int ix = 0; ix < std::min(S.size(), all[i].size()); ix++)
      |                              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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