Submission #978005

#	Time	Username	Problem	Language	Result	Execution time	Memory
978005		canadavid1	Combo (IOI18_combo)	C++17	100 / 100	15 ms	2028 KiB

combo

#include "combo.h"

#include <random>
#include <algorithm>
#include <utility>
#include <iostream>
#include <vector>
int press2(std::string s)
{
    // std::cout << s << std::endl;
    return press(s);
}
std::string guess_sequence(int N) {
    std::mt19937 rng(12345);
    std::string S;
    if(press2("AB")) if(press2("A")) S = "A";
                    else S = "B";
    else            if(press2("X")) S = "X";
                    else S = "Y";
    
    std::vector<char> o;
    for(char i : "ABXY") if (S[0]!=i) o.push_back(i);
    std::vector<char> o2 = o;
    if(false) for(;S.size()*6+14<=4*N;)
    {
        //std::shuffle(o.begin(),o.end(),rng);
        //std::shuffle(o2.begin(),o2.end(),rng);
        //std::cerr << o << " " << o2 << "\n";
        std::string guess =   S + o[0] 
                            + S + o[1] + o2[0] + S + o[1] + o2[1] 
                            + S + o[1] + o2[2] + o[0]
                            + S + o[1] + o2[2] + o[1]
                            + S + o[1] + o2[2] + o[2];
        switch(press2(guess)-S.size())
        {
            case 0:S.push_back(o[2]);break;
            case 1:S.push_back(o[0]);break;
            case 2:S.push_back(o[1]);break;
            case 3:
                S.push_back(o[1]);
                S.push_back(o2[2]);
                break;
            default:
                break;
        }
    }
    for(;S.size()<N-1;)
    {
        std::string guess =   S + o[0] 
                            + S + o[1] + o2[0] + S + o[1] + o2[1] + S + o[1] + o2[2];
        switch(press2(guess)-S.size())
        {
            case 0:S.push_back(o[2]);break;
            case 1:S.push_back(o[0]);break;
            case 2:S.push_back(o[1]);break;
            default:
                break;
        }
    }
    if(N==1) return S;
    if(press2(S+o[0])==N) S.push_back(o[0]);
    else if (press2(S+o[1])==N) S.push_back(o[1]);
    else S.push_back(o[2]);
    return S;
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:24:33: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     if(false) for(;S.size()*6+14<=4*N;)
      |                    ~~~~~~~~~~~~~^~~~~
combo.cpp:47:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     for(;S.size()<N-1;)
      |          ~~~~~~~~^~~~

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