Submission #746452

#	Time	Username	Problem	Language	Result	Execution time	Memory
746452		pls33	Combo (IOI18_combo)	C++17	30 / 100	52 ms	588 KiB

combo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
template <typename F>
void _debug(F f)
{
    f();
}

#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

#ifndef _AAAAAAAAA
#include "combo.h"
#else
std::string guess_sequence(int N);
int press(std::string p);
#endif

void guess_separator(string s, char &c)
{
    if (s.size() == 1)
    {
        c = s[0];
        return;
    }

    string l = s.substr(0, s.size() / 2);
    string r = s.substr(s.size() / 2, s.size() / 2);

    if (press(l))
    {
        guess_separator(l, c);
    }
    else
    {
        guess_separator(r, c);
    }
}

std::string guess_sequence(int N)
{
    mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
    char separator = 0;
    string button = "ABXY";
    guess_separator(button, separator);

    button.erase(find(button.begin(), button.end(), separator));

    string result;
    result += separator;

    vector<string> q(3);
    for (int i = 2; i <= N; i++)
    {
        shuffle(button.begin(), button.end(), rng);
        for (int j = 0; j < 3; j++)
        {
            q[j] = result + button[j];
        }

        if (press(q[0] + q[1]) == i)
        {
            if (press(q[0]) == i)
            {
                result += button[0];
            }
            else
            {
                result += button[1];
            }
        }
        else
        {
            result += button[2];
        }
    }

    return result;
}

#ifdef _AAAAAAAAA

namespace
{

    constexpr int MAX_N = 2000;
    constexpr int MAX_NUM_MOVES = 8000;

    int N;
    std::string S;

    int num_moves;

    void wrong_answer(const char *MSG)
    {
        printf("Wrong Answer: %s\n", MSG);
        exit(0);
    }

} // namespace

int press(std::string p)
{
    if (++num_moves > MAX_NUM_MOVES)
    {
        wrong_answer("too many moves");
    }
    int len = (int)p.length();
    if (len > 4 * N)
    {
        wrong_answer("invalid press");
    }
    for (int i = 0; i < len; ++i)
    {
        if (p[i] != 'A' && p[i] != 'B' && p[i] != 'X' && p[i] != 'Y')
        {
            wrong_answer("invalid press");
        }
    }
    int coins = 0;
    for (int i = 0, j = 0; i < len; ++i)
    {
        if (j < N && S[j] == p[i])
        {
            ++j;
        }
        else if (S[0] == p[i])
        {
            j = 1;
        }
        else
        {
            j = 0;
        }
        coins = std::max(coins, j);
    }
    return coins;
}

int main()
{
    freopen("combo.in", "r", stdin);
    char buffer[MAX_N + 1];
    if (scanf("%s", buffer) != 1)
    {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
    }
    S = buffer;
    N = (int)S.length();

    num_moves = 0;
    std::string answer = guess_sequence(N);
    if (answer != S)
    {
        wrong_answer("wrong guess");
        exit(0);
    }
    printf("Accepted: %d\n", num_moves);
    return 0;
}

#endif

Compilation message (stderr)

combo.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
combo.cpp:43: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   43 | #pragma endregion
      |

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