Submission #545781

#	Time	Username	Problem	Language	Result	Execution time	Memory
545781		Sergio_2357	Combo (IOI18_combo)	C++17	30 / 100	38 ms	760 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, int n)
{
    if (s.size() == n - 1) {
        return s + a + s + b;
    }
    vector<string> qs = {
        { a, a }, { a, b }, { b, a }, { b, b }
    };
    string res = "";
    for (int i = 0; i < qs.size(); i++)
        res += s + qs[i];
    return res;
}

string guess_sequence(int N)
{
    srand(time(NULL));
    //Pseudocode:
    char f_l = get_f_l();
    string s = "";
    s.push_back(f_l);
    char a, b, c;
    assign_chars(f_l, a, b, c);
    while (s.size() < N) {
        // ask for aa, ab, ba, bb
        swap_c(a, b, c);
        string q = gen_q(s, a, b, N);
        int r = press(q) - s.size();
        //If r == 0, we know c is the answer;
        if (r == 0)
            s.push_back(c);
        //If r == 1, we know either a or b are the answer in this round, and that c is the answer in the next one;
        if (r == 1) {
            if (press(s + a) - s.size())
                s.push_back(a);
            else
                s.push_back(b);
            s.push_back(c);
        }
        //If r == 2, we know a or b are the answer in this and in the next round;
        if (r == 2) {
            if (press(s + a) - s.size())
                s.push_back(a);
            else
                s.push_back(b);
            if (press(s + a) - s.size())
                s.push_back(a);
            else
                s.push_back(b);
        }
    }
    s.resize(N);
    return s;
}

Compilation message (stderr)

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

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