Submission #126755

#	Time	Username	Problem	Language	Result	Execution time	Memory
126755		wasyl	Combo (IOI18_combo)	C++11	100 / 100	53 ms	604 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>
using namespace std;

string guess_sequence(const int n)
{
    char tab[] = {'A', 'B', 'X', 'Y'};

    vector< int > pos(4);
    iota(begin(pos), end(pos), 0);

    while (pos.size() > 1)
    {
        int mi = pos.size() / 2;
        vector< int > que;
        string r;
        for (int i = 0; i < mi; ++i)
            r += string(1, tab[pos[i]]);
        if (press(r))
            pos.erase(begin(pos) + mi, end(pos));
        else
            pos.erase(begin(pos), begin(pos) + mi);
    }

    vector< int > ilo(4);
    iota(begin(ilo), end(ilo), 0);

    for (int i = 0; i < ilo.size(); ++i)
        if (ilo[i] == pos[0])
        {
            ilo.erase(begin(ilo) + i);
            break;
        }
    
    string r = string(1, tab[pos[0]]);

    for (int i = 2; i <= n - 1; ++i)
    {
        string q;
        q += r + string(1, tab[ilo[1]]);
        for (int j = 0; j < ilo.size(); ++j)
            q += r + string(1, tab[ilo[2]]) + string(1, tab[ilo[j]]);
        int a = press(q);
        r += string(1, tab[ilo[a - (i - 1)]]);
    }

    if (n > 1)
    {
        vector< int > kan = ilo;

        while (kan.size() > 1)
        {
            int mi = kan.size() / 2;
            string q;
            for (int i = 0; i < mi; ++i)
                q += r + string(1, tab[kan[i]]);
            if (press(q) == n)
                kan.erase(begin(kan) + mi, end(kan));
            else
                kan.erase(begin(kan), begin(kan) + mi);
        }
        r += string(1, tab[kan[0]]);
    }

    //cerr << r << '\n';
    return r;
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < ilo.size(); ++i)
      |                     ~~^~~~~~~~~~~~
combo.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j = 0; j < ilo.size(); ++j)
      |                         ~~^~~~~~~~~~~~

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