Submission #772618

#	Time	Username	Problem	Language	Result	Execution time	Memory
772618		_martynas	Combo (IOI18_combo)	C++11	100 / 100	24 ms	636 KiB

combo

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

using namespace std;

/*
Let known prefix be $ and first letter is A
press: $B + $XX + $XB + $XY
if this string returns |$|+1 then $ = $+'B'
else if this string returns |$|+2 then $ = $+'X'
else $ = $+'Y'
*/

string guess_sequence(int N) {
    vector<char> C = {'A', 'B', 'X', 'Y'};
    if(N == 1) {
        C.pop_back();
        for(char c : C) {
            if(press(string(1, c))) {
                return string(1, c);
            }
        }
        return string(1, 'Y');
    }
    string p = "AB";
    string S = "";
    if(press(p)) {
        p = "A";
        if(press(p)) S = "A";
        else S = "B";
    }
    else {
        p = "X";
        if(press(p)) S = "X";
        else S = "Y";
    }
    for(int i = 0; i < N-2; i++) {
        p = "";
        string temp = "";
        for(char c : C) {
            if(c == S[0]) continue;
            if(p == "") {
                p = S; p += c;
                temp += c;
            }
            else if(p.size() == S.size()+1) {
                for(char cc : C) {
                    if(cc == S[0]) continue;
                    p += S; p += c; p += cc;
                }
                temp += c;
            }
            else {
                temp += c;
            }
        }
        int val = press(p);
        if(val == S.size()+1) {
            S += temp[0];
        }
        else if(val == S.size()+2) {
            S += temp[1];
        }
        else {
            S += temp[2];
        }
    }
    int cnt = 0;
    for(char c : C) {
        if(c == S[0]) continue;
        cnt++;
        if(cnt == 3) {
            S += c;
        }
        else {
            p = S; p += c;
            if(press(p) == N) {
                S += c; break;
            }
        }
    }
    return S;
}
/*

*/

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(val == S.size()+1) {
      |            ~~~~^~~~~~~~~~~~~
combo.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         else if(val == S.size()+2) {
      |                 ~~~~^~~~~~~~~~~~~

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