Submission #580296

#	Time	Username	Problem	Language	Result	Execution time	Memory
580296		drdilyor	Combo (IOI18_combo)	C++17	100 / 100	39 ms	612 KiB

combo

#if defined(ONPC) && !defined(_GLIBCXX_ASSERTIONS)
    #define _GLIBCXX_ASSERTIONS
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#ifdef ONPC
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
#define allit(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())
#include "combo.h"

using namespace std;
using ll = long long;
using vi = vector<int>;
namespace pd = __gnu_pbds;
template<typename K>
using ordered_set = pd::tree<K, pd::null_type, less<int>, pd::rb_tree_tag, pd::tree_order_statistics_node_update>;
template<typename... T>
using gp_hash_table = pd::gp_hash_table<T...>;//simple using statement gives warnings

const int INF = 1e9;
const ll INFL = 1e18;
const int N = 1e5;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);

string order = "ABXY";
void shuffle() {
    for (int i = 0; i < sz(order)-1; i++) {
        swap(order[i], order[i + rng()%(sz(order)-i)]);
    }
}

string guess_sequence(int n) {
    string res;
    shuffle();
    if (press(order.substr(0, 2))) {
        if (press(order.substr(0, 1))) res += order[0];
        else res += order[1];
    } else {
        if (press(order.substr(2, 1))) res += order[2];
        else res += order[3];
    }
    for (int i = 0, j = 0; i < sz(order); i++) {
        if (order[i] != res.front()) order[j++] = order[i];
    }
    order.resize(sz(order)-1);

    for (int i = 1; i < n-1; i++) {
        shuffle();
        string q = res + order[1];
        for (int i = 0; i < sz(order); i++) q += res + order[0] + order[i];
        int coins = press(q);

        if (coins == i+2) {
            res += order[0];
        } else if (coins == i+1) {
            res += order[1];
        } else {
            res += order[2];
        }
    }
    if (res.size() != n) {
        if (press(res + order[0] + res + order[1]) == n) {
            if (press(res + order[0]) == n) res += order[0];
            else res += order[1];
        } else {
            res += order[2];
        }
    }

    return res;
}

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:67:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |     if (res.size() != n) {
      |         ~~~~~~~~~~~^~~~

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