Submission #497244

#	Time	Username	Problem	Language	Result	Execution time	Memory
497244		pakhomovee	콤보 (IOI18_combo)	C++17	97 / 100	36 ms	636 KiB

combo

#include "combo.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>

using namespace std;

int press(string p);

string guess_sequence(int N) {
    mt19937 rnd;
    vector<char> v = { 'A', 'B', 'X', 'Y' };
    shuffle(v.begin(), v.end(), rnd);
    string res;
    for (int i = 0; i < 3; ++i) {
        string curr;
        curr += v[i];
        if (press(curr)) {
            res += v[i];
            break;
        }
    }
    if (res.size() == 0) {
        res += v.back();
    }
    v.erase(find(v.begin(), v.end(), res[0]));
    int ptr = 1;
    while (ptr + 1 < N) {
        string query = res;
        query += v[0];
        query += res;
        query += v[1];
        query += v[0];
        query += res;
        query += v[1];
        query += v[1];
        query += res;
        query += v[1];
        query += v[2];
        assert(query.size() <= N * 4);
        int c = press(query);
        if (c == ptr) {
            res += v[2];
        } else if (c == ptr + 1) {
            res += v[0];
        } else {
            res += v[1];
        }
        ++ptr;
    }
    if (ptr < N) {
        for (int i = 0; i < 2; ++i) {
            string curr = res;
            curr += v[i];
            if (press(curr) == N) {
                res += v[i];
                break;
            }
        }
        if (res.size() < N) {
            res += v[2];
        }
    }
    v = { 'A', 'B', 'X', 'Y' };
    return res;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from combo.cpp:4:
combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:41:29: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         assert(query.size() <= N * 4);
      |                ~~~~~~~~~~~~~^~~~~~~~
combo.cpp:61:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if (res.size() < N) {
      |             ~~~~~~~~~~~^~~

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