Submission #713136

#	Time	Username	Problem	Language	Result	Execution time	Memory
713136		lmqzzz	Combo (IOI18_combo)	C++14	100 / 100	33 ms	724 KiB

combo

#include "combo.h"

#include <bits/stdc++.h>
using namespace std;

string button = "ABXY";

std::string guess_sequence(int N) {
        string ans = "";
        char first;
        if (press("AB")) {
                first = press("A") ? 'A' : 'B';
        } else {
                first = press("X") ? 'X' : 'Y';
        }
        for (int i = 0; i < 4; i++) {
                if (button[i] == first) {
                        button.erase(button.begin() + i);
                        break;
                }
        }
        // cerr << button << '\n';
        assert(button.size() == 3);
        ans += first;
        int special_case = 0;
        for (int j = 1; j <= N - 2; j++) {
                string ask = "";
                string aa = ans, ab = ans, ac = ans, ba = ans;
                if (special_case) aa += button[0];
                if (special_case) ab += button[0];
                if (special_case) ac += button[0];
                if (special_case) ba += button[0];
                aa = (aa + button[0]) + button[0];
                ab = (ab + button[0]) + button[1];
                ac = (ac + button[0]) + button[2];
                ba = (ba + button[1]) + button[0];
                ask = aa + ab + ac + ba;
                assert(ask.size() <= N * 4);
                int x = press(ask);
                // cerr << j << ' ' << special_case << ' ' << ask << ' ' << x << '\n';
                if (special_case) {
                        assert(x >= j - 1);
                        if (x == j - 1) {
                                ans += button[1];
                                ans += button[0];
                                special_case = 0;
                        } else if (x == j) {
                                ans += button[0];
                                ans += button[2];
                                special_case = 0;
                        } else if (x == j + 1) {
                                ans += button[0];
                                ans += button[1];
                                special_case = 0;
                        } else {
                                ans += button[0];
                        }
                } else {
                        assert(x >= j);
                        if (x == j) {
                                ans += button[2];
                        } else if (x == j + 1) {
                                ans += button[1];
                        } else {
                                special_case = 1;
                        }
                }
        }
        if (N == 1) return ans;
        if (special_case) {
                assert(ans.size() + 2 == N);
                string aa = (ans + button[0]) + button[0];
                string ab = (ans + button[0]) + button[1];
                string ac = (ans + button[0]) + button[2];
                string ba = (ans + button[1]) + button[0];
                if (press(aa + ab) == N) {
                        if (press(aa) == N) {
                                ans = aa;
                        } else {
                                ans = ab;
                        }
                } else {
                        if (press(ac) == N) {
                                ans = ac;
                        } else {
                                ans = ba;
                        }
                }
        } else {
                assert(ans.size() + 1 == N);
                if (press(ans + button[0]) == N) {
                        ans += button[0];
                } else if (press(ans + button[1]) == N) {
                        ans += button[1];
                } else {
                        ans += button[2];
                }
        }
        return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from combo.cpp:3:
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:38:35: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |                 assert(ask.size() <= N * 4);
      |                        ~~~~~~~~~~~^~~~~~~~
combo.cpp:71:39: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |                 assert(ans.size() + 2 == N);
      |                        ~~~~~~~~~~~~~~~^~~~
combo.cpp:90:39: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |                 assert(ans.size() + 1 == N);
      |                        ~~~~~~~~~~~~~~~^~~~

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