제출 #580294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580294		drdilyor	콤보 (IOI18_combo)	C++17	5 / 100	1 ms	208 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 (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;
}

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