Submission #790471

#	Time	Username	Problem	Language	Result	Execution time	Memory
790471		Boas	Combo (IOI18_combo)	C++17	0 / 100	1 ms	336 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};
    vector<int> isKnown(5 * N); // 0: not known, 1: = button[0], -1: !button[1]
    while (S.size() < N)
    {
        // int newTotal = all.size() * 3;
        // int halfTotal = (newTotal + 1) / 2;
        // int newSize = all[0].size() + 1;
        auto oldAll(all);
        while (all[0].size() * all.size() / 3 <= 4 * N)
        {
            oldAll = vector<string>(all);
            // cerr << "newTotal: " << newTotal << endl;
            // cerr << "halfTotal: " << halfTotal << endl;
            // cerr << "newSize: " << newSize << endl;
            if (all[0].size() > N)
                break;
            // cerr << halfTotal * newSize << " < " << 4 * N << endl;
            int s = all.size();
            for (int i = 0; i < s; i++)
            {
                if (isKnown[all[0].size()] == 0)
                {
                    all.push_back(all[i] + buttons[1]);
                    all.push_back(all[i] + buttons[2]);
                    all[i] += buttons[0];
                }
                else if (isKnown[all[0].size()] == 1)
                {
                    all[i] += buttons[0];
                }
                else
                {
                    all.push_back(all[i] + buttons[2]);
                    all[i] += buttons[1];
                }
            }
            if (all[0].size() > N)
                break;

            // newTotal = all.size() * 3;
            // halfTotal = (newTotal + 1) / 2;
            // newSize = all[0].size() + 1;
        }
        all = vector<string>(oldAll);
        int k = all.size() / 3;
        string p;
        p.reserve(4 * N);
        vector<string> guesses(all.begin(), all.begin() + k);
        int l = k * all[0].size();
        // resterende ruimte opvullen met random junk
        int index = 0;
        while (l < 4 * N)
        {
            string add{buttons[0]};
            guesses[index] += add;
            l++;
            index++;
            index %= k;
        }
        for (int i = 0; i < k; i++)
        {
            if (i >= guesses.size())
            {
                cout << "this shouldn't happen!";
                break;
            }
            p += guesses[i];
        }
        int res = press(p);
        if (res >= all[0].size())
        {
            all.erase(all.begin() + k, all.end());
            if (res > all[0].size())
            {
                for (int i = all[0].size(); i < res; i++)
                {
                    isKnown[i] = 1;
                }
            }
            else
            {
                isKnown[all[0].size()] = -1;
            }
        }
        else
        {
            if (res > S.size())
            {
                string common = guesses[0];
                common.erase(common.begin() + res, common.end());
                for (int i = 1; i < guesses.size(); i++)
                {
                    for (int ix = 0; ix < std::min(common.size(), guesses[i].size()); ix++)
                    {
                        if (common[ix] != guesses[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 = (int)all.size() - 1; i > 0; 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:24:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     while (S.size() < N)
      |            ~~~~~~~~~^~~
combo.cpp:30:47: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         while (all[0].size() * all.size() / 3 <= 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:58:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |             if (all[0].size() > N)
      |                 ~~~~~~~~~~~~~~^~~
combo.cpp:83:19: 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]
   83 |             if (i >= guesses.size())
      |                 ~~^~~~~~~~~~~~~~~~~
combo.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if (res >= all[0].size())
      |             ~~~~^~~~~~~~~~~~~~~~
combo.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             if (res > all[0].size())
      |                 ~~~~^~~~~~~~~~~~~~~
combo.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             if (res > S.size())
      |                 ~~~~^~~~~~~~~~
combo.cpp:112: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]
  112 |                 for (int i = 1; i < guesses.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~~
combo.cpp:114:41: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  114 |                     for (int ix = 0; ix < std::min(common.size(), guesses[i].size()); ix++)
      |                                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
combo.cpp:124: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]
  124 |                 for (int i = 0; i < all.size(); i++)
      |                                 ~~^~~~~~~~~~~~
combo.cpp:126:41: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  126 |                     for (int ix = 0; ix < std::min(common.size(), all[i].size()); ix++)
      |                                      ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
combo.cpp:143:33: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  143 |             for (int ix = 0; ix < std::min(S.size(), all[i].size()); ix++)
      |                              ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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