Submission #545838

#	Time	Username	Problem	Language	Result	Execution time	Memory
545838		Sergio_2357	Combo (IOI18_combo)	C++17	100 / 100	39 ms	660 KiB

combo

#include "combo.h"
#include <bits/stdc++.h>

using namespace std;

char get_f_l()
{
    char a, b, c, d;
    a = 'A';
    b = 'B';
    c = 'X';
    d = 'Y';
    if (press({ a, b })) {
        if (press({ a }))
            return a;
        else
            return b;
    } else {
        if (press({ c }))
            return c;
        else
            return d;
    }
}

void assign_chars(char f, char& a, char& b, char& c)
{
    string s = "ABXY";
    int d = 0;
    while (f != s[d])
        d++;
    string r = "";
    for (int i = 0; i < 4; i++) {
        if (i == d)
            continue;
        r.push_back(s[i]);
    }
    a = r[0];
    b = r[1];
    c = r[2];
}

void swap_c(char& a, char& b, char& c)
{
    string s = { a, b, c };
    random_shuffle(s.begin(), s.end());
    a = s[0];
    b = s[1];
    c = s[2];
}

string gen_q(string s, char a, char b, char c, int n)
{
    vector<string> qs = {
        { a }, { b, a }, { b, b }, { b, c }
    };
    string res = "";
    for (int i = 0; i < qs.size(); i++)
        res += s + qs[i];
    return res;
}

string guess_sequence(int N)
{
    srand(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());
    //Pseudocode:
    char f_l = get_f_l();
    string s = "";
    s.push_back(f_l);
    if (N == 1)
        return s;
    char a, b, c;
    assign_chars(f_l, a, b, c);
    while (s.size() < N - 1) {
        // ask for a, ba, bb, bc
        //swap_c(a, b, c);
        string q = gen_q(s, a, b, c, N);
        int r = press(q) - s.size();
        if (r == 0)
            s.push_back(c);
        if (r == 1)
            s.push_back(a);
        if (r == 2)
            s.push_back(b);
    }
    if (press(s + a) - s.size())
        s.push_back(a);
    else if (press(s + b) - s.size())
        s.push_back(b);
    else
        s.push_back(c);
    s.resize(N);
    return s;
}

Compilation message (stderr)

combo.cpp: In function 'std::string gen_q(std::string, char, char, char, int)':
combo.cpp:58:23: 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]
   58 |     for (int i = 0; i < qs.size(); i++)
      |                     ~~^~~~~~~~~~~
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:74:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     while (s.size() < N - 1) {
      |            ~~~~~~~~~^~~~~~~

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