Submission #1031508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031508		ArthuroWich	Combo (IOI18_combo)	C++17	30 / 100	36 ms	2280 KiB

combo

#include "combo.h"
#include<bits/stdc++.h>
using namespace std;
string guess_sequence(int n) {
    string s;
    int v;
    v = press("AB");
    if (v == 2) {
        s = "AB";
    } else if (v == 1) {
        v = press("A");
        if (v == 1) {
            s = "A";
        } else {
            s = "B";
        }
    } else {
        v = press("XY");
        if (v == 2) {
            s = "XY";
        } else {
            v = press("X");
            if (v == 1) {
                s = "X";
            } else {
                s = "Y";
            }
        }
    }
    if (n == 1) {
        return s;
    } else if (s.length() == n) {
        return s;
    }
    vector<string> alp;
    for (char c : "ABXY") {
        if (c != s[0]) {
            string t = "";
            t.push_back(c);
            alp.push_back(t);
        }
    }
    while(s.length() != n) {
        int si = 0, a = 1;
        while((si+1+s.length())*a <= 4*n) {
            si++;
            a *= 3;
        }
        si = min(si, n-(int)s.length());
        vector<vector<string>> c(si);
        c[0].push_back(s+alp[0]);
        c[0].push_back(s+alp[1]);
        c[0].push_back(s+alp[2]);
        for (int i = 1; i < si; i++) {
            for (string e : c[i-1]) {
                c[i].push_back(e+alp[0]);
                c[i].push_back(e+alp[1]);
                c[i].push_back(e+alp[2]);
            }
        }
        int ch = s.length()+si;
        int l = 0, r = c[si-1].size()-1;
        while(l < r) {
            int m1 = l+(r-l+1)/3, m2 = l+2*(r-l+1)/3;
            string s1 = "";
            for (int i = l; i < m1; i++) {
                s1 += c[si-1][i];
            }
            if (press(s1) == ch) {
                r = m1-1;
                continue;
            }
            s1 = "";
            for (int i = m1; i < m2; i++) {
                s1 += c[si-1][i];
            }
            if (press(s1) == ch) {
                l = m1;
                r = m2-1;
            } else {
                l = m2;
            }
        }
        v = s.length();
        for (int i = v; i < c[si-1][l].length(); i++) {
            s.push_back(c[si-1][l][i]);
        }
    }
    return s;
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:32:27: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |     } else if (s.length() == n) {
      |                ~~~~~~~~~~~^~~~
combo.cpp:43:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     while(s.length() != n) {
      |           ~~~~~~~~~~~^~~~
combo.cpp:45:35: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         while((si+1+s.length())*a <= 4*n) {
      |               ~~~~~~~~~~~~~~~~~~~~^~~~~~
combo.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int i = v; i < c[si-1][l].length(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

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