Random Testing
(utilities/random_testing.hpp)

• View this file on GitHub
• Last update: 2026-08-11 14:24:35+09:00
• Include: #include "utilities/random_testing.hpp"

The Quick Way

You do not need to rewrite a solution to return custom input and answer types. Keep ordinary contest code that reads std::cin and writes std::cout:

void solve() {
    // The same code used in the submission.
}

Then choose one helper:

Problem	Helper
Non-interactive or constructive	stream_stress_test(generate, solve, check)
Interactive	interactive_stream_stress_test(limit, generate, solve, reply, check)

The helper redirects std::cin and std::cout for every random case. You only write the random input generator and checker. On failure it prints the input, output or interaction transcript, seed, and zero-based trial.

#include "utilities/random_testing.hpp"

using namespace m1une::utilities;

Non-Interactive and Constructive Recipe

Write these three pieces:

auto generate = [](Random& random, std::ostream& input) {
    // Write one small random case to input.
};

void solve() {
    // Read std::cin and write std::cout as usual.
}

auto check = [](std::istream& input, std::istream& output) {
    // Read the original input and candidate output.
    return true;  // Return whether the output is valid.
};

int main() {
    stream_stress_test(generate, solve, check);
}

This works for constructive problems because check validates the output; it does not compare against one fixed answer.

Complete example

The following tester checks ordinary code that prints the values in sorted order:

#include "utilities/random_testing.hpp"

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace m1une::utilities;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> values(n);
    for (int& value : values) std::cin >> value;

    std::sort(values.begin(), values.end());
    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
}

int main() {
    auto generate = [](Random& random, std::ostream& input) {
        int n = int(random.uniform(0, 20));
        input << n << '\n';
        for (int value : random.sequence(n, -10, 10)) {
            input << value << ' ';
        }
        input << '\n';
    };

    auto check = [](std::istream& input, std::istream& output) {
        int n;
        input >> n;
        std::vector<int> expected(n);
        for (int& value : expected) input >> value;
        std::sort(expected.begin(), expected.end());

        std::vector<int> actual(n);
        for (int& value : actual) {
            if (!(output >> value)) return false;
        }
        std::string extra;
        return actual == expected && !(output >> extra);
    };

    stream_stress_test(generate, solve, check);
}

Usually the generator is just a few random.uniform(...) calls and << operations. The checker can reuse input constraints and validation logic from the problem statement.

The default is 1000 cases with a fixed seed. Add a trial count and seed at the end when needed:

stream_stress_test(generate, solve, check, 10000, 123456789);

Interactive Recipe

The submitted solution can keep the ordinary protocol:

std::cout << "? " << query << std::endl;
std::cin >> reply;
// ...
std::cout << "! " << answer << std::endl;

The tester needs four pieces:

1. generate writes the public input and returns hidden judge state;
2. solve is the ordinary interactive solution;
3. reply reads one query and writes the mock judge’s response;
4. check validates the final output.

Complete example

#include "utilities/random_testing.hpp"

#include <iostream>
#include <string>

using namespace m1une::utilities;

void solve() {
    int upper;
    std::cin >> upper;

    int low = 0;
    int high = upper;
    while (low < high) {
        int middle = (low + high) / 2;
        std::cout << "? " << middle << std::endl;

        int comparison;
        std::cin >> comparison;
        if (comparison <= 0) high = middle;
        else low = middle + 1;
    }
    std::cout << "! " << low << std::endl;
}

int main() {
    auto generate = [](Random& random, std::ostream& input) {
        int upper = 1000;
        input << upper << '\n';
        return int(random.uniform(0, upper));  // Hidden number.
    };

    auto reply = [](int& secret, std::istream& query,
                    std::ostream& response) {
        char type;
        int guess;
        std::string extra;
        if (!(query >> type >> guess) || type != '?' || query >> extra) {
            reject_query("expected: ? x");
        }

        if (secret < guess) response << -1;
        else if (guess < secret) response << 1;
        else response << 0;
    };

    auto check = [](std::istream& input, const int& secret,
                    std::istream& output) {
        int upper;
        char type;
        int answer;
        std::string extra;
        input >> upper;
        return bool(output >> type >> answer) && type == '!' &&
               0 <= answer && answer <= upper && answer == secret &&
               !(output >> extra);
    };

    interactive_stream_stress_test(10, generate, solve, reply, check);
}

When solve tries to read after printing, the helper sends that pending output to reply and feeds the generated response back through std::cin. Output remaining when solve returns is passed to check as the final answer.

Call reject_query("reason") for malformed or forbidden queries. The first query beyond the limit also fails. Both failures include the full query/reply transcript.

Select trials and a seed with trailing arguments:

interactive_stream_stress_test(
    query_limit, generate, solve, reply, check, 10000, 123456789);

Practical Limitations

The stream helpers redirect C++ std::cin and std::cout. They cannot capture scanf, printf, fread, FastInput, or other code that accesses the C file handles directly. Keep a std::cin/std::cout version while stress testing, or move only the algorithm into a shared function used by both I/O frontends.

Call std::ios::sync_with_stdio(false) before starting the tester, not inside solve, because changing synchronization can replace standard stream buffers.

The interactive helper runs in one process without real pipes. It checks the algorithm and protocol, but it does not detect missing flushes, deadlocks, or timing problems.

Typed Helpers (Optional)

Use the typed interface only when the solution already accepts values and returns an answer.

For ordinary optimized-vs-brute testing:

stress_test(generate, solve, brute);

For constructive testing:

constructive_stress_test(
    generate,
    solve,
    [](const Input& input, const Answer& answer) {
        return is_valid(input, answer);
    });

For a typed interactive solution, generate public input and hidden state with interactive_test_case(input, state). The solution receives the public input and an object providing interaction.ask(query):

interactive_stress_test(
    query_limit, generate, solve, reply, check);

The stream and typed interfaces use the same deterministic seeds, failure categories, query limits, and transcript reporting.

Handle Failure Without Aborting

The *_stress_test helpers print a failure and call std::abort. Use the lower-level version to inspect a result instead:

RandomTestConfig config;
config.trials = 10000;
config.seed = 123456789;

auto result = test_streams(config, generate, solve, check);
if (!result) {
    // result.seed
    // result.failed_trial
    // result.failure
}

The interactive equivalent is:

auto result = test_interactive_streams(
    config, query_limit, generate, solve, reply, check);

Result field	Meaning
seed	Seed used by the generator.
requested_trials	Number of requested cases.
completed_trials	Cases that passed before the failure.
failed_trial	Zero-based failed case, or -1 on success.
failure	property, mismatch, rejected_output, query_limit, or invalid_query.
query_count	Attempted queries on an interactive failure, otherwise -1.

result.passed() and bool(result) report success.

Interface Reference

template <class Generator, class Solution, class Checker>
RandomTestResult stream_stress_test(
    Generator generator,
    Solution solution,
    Checker checker,
    int trials = 1000,
    std::uint64_t seed = default_random_test_seed);

template <class Generator, class Solution, class QueryHandler, class Checker>
RandomTestResult interactive_stream_stress_test(
    int query_limit,
    Generator generator,
    Solution solution,
    QueryHandler query_handler,
    Checker checker,
    int trials = 1000,
    std::uint64_t seed = default_random_test_seed);

The lower-level forms add a configuration and optional failure callback:

template <class Generator, class Solution, class Checker,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_streams(
    RandomTestConfig config,
    Generator generator,
    Solution solution,
    Checker checker,
    OnFailure on_failure = {});

template <class Generator, class Solution, class QueryHandler, class Checker,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_interactive_streams(
    RandomTestConfig config,
    int query_limit,
    Generator generator,
    Solution solution,
    QueryHandler query_handler,
    Checker checker,
    OnFailure on_failure = {});

The non-interactive callback is called as on_failure(input_text, output_text, trial, seed). The interactive callback is called as on_failure(input_text, state, transcript, trial, seed, failure).

Generators may also accept a final int trial. The non-interactive generator returns void; the interactive generator returns the hidden state. Query handlers return void and write their response to the supplied output stream.

The harness adds $O(1)$ work per trial apart from the supplied functions and the size of generated/captured text. Interactive transcript time and memory are linear in the total query and response text.

Depends on

• Random (utilities/random.hpp)

Verified with

• verify/utilities/random_testing.test.cpp

Code

#ifndef M1UNE_RANDOM_TESTING_HPP
#define M1UNE_RANDOM_TESTING_HPP 1

#include <cassert>
#include <concepts>
#include <cstdint>
#include <cstdlib>
#include <exception>
#include <functional>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#include "random.hpp"

namespace m1une {
namespace utilities {

inline constexpr std::uint64_t default_random_test_seed =
    0x243f6a8885a308d3ULL;

struct RandomTestConfig {
    int trials = 1000;
    std::uint64_t seed = default_random_test_seed;
};

enum class RandomTestFailure {
    none,
    property,
    mismatch,
    rejected_output,
    query_limit,
    invalid_query,
};

inline const char* random_test_failure_name(RandomTestFailure failure) {
    switch (failure) {
        case RandomTestFailure::none:
            return "none";
        case RandomTestFailure::property:
            return "property";
        case RandomTestFailure::mismatch:
            return "mismatch";
        case RandomTestFailure::rejected_output:
            return "rejected output";
        case RandomTestFailure::query_limit:
            return "query limit exceeded";
        case RandomTestFailure::invalid_query:
            return "invalid query";
    }
    return "unknown";
}

struct RandomTestResult {
    std::uint64_t seed = 0;
    int requested_trials = 0;
    int completed_trials = 0;
    int failed_trial = -1;
    RandomTestFailure failure = RandomTestFailure::none;
    int query_count = -1;

    bool passed() const {
        return failed_trial == -1;
    }

    explicit operator bool() const {
        return passed();
    }
};

struct IgnoreRandomTestFailure {
    template <class... Args>
    void operator()(Args&&...) const {}
};

struct InteractionExchange {
    std::string query;
    std::string response;
    bool responded = false;
};

struct InteractionTranscript {
    std::vector<InteractionExchange> exchanges;
    std::string answer;
    bool answered = false;
    std::string failure_message;
};

namespace random_testing_detail {

template <class T>
void print_value(std::ostream& output, const T& value) {
    if constexpr (requires { output << value; }) {
        output << value;
    } else if constexpr (requires {
                             typename std::tuple_size<
                                 std::remove_cvref_t<T>>::type;
                         }) {
        output << '(';
        int index = 0;
        std::apply(
            [&](const auto&... elements) {
                ((output << (index++ == 0 ? "" : ", "),
                  print_value(output, elements)),
                 ...);
            },
            value);
        output << ')';
    } else if constexpr (requires { std::begin(value); std::end(value); }) {
        output << '[';
        bool first = true;
        for (const auto& element : value) {
            if (!first) output << ", ";
            first = false;
            print_value(output, element);
        }
        output << ']';
    } else {
        output << "<unprintable>";
    }
}

template <class Function>
decltype(auto) invoke_with_trial(Function& function, Random& random, int trial) {
    if constexpr (std::invocable<Function&, Random&, int>) {
        return std::invoke(function, random, trial);
    } else {
        static_assert(std::invocable<Function&, Random&>);
        return std::invoke(function, random);
    }
}

inline RandomTestResult success_result(const RandomTestConfig& config) {
    RandomTestResult result;
    result.seed = config.seed;
    result.requested_trials = config.trials;
    result.completed_trials = config.trials;
    return result;
}

inline RandomTestResult failure_result(const RandomTestConfig& config,
                                       int failed_trial,
                                       RandomTestFailure failure,
                                       int query_count = -1) {
    RandomTestResult result;
    result.seed = config.seed;
    result.requested_trials = config.trials;
    result.completed_trials = failed_trial;
    result.failed_trial = failed_trial;
    result.failure = failure;
    result.query_count = query_count;
    return result;
}

template <class T>
std::string value_to_string(const T& value) {
    std::ostringstream output;
    print_value(output, value);
    return output.str();
}

struct InteractionAbort {
    RandomTestFailure failure;
    std::string message;
};

class StandardStreamRedirect {
   private:
    std::streambuf* _cin_buffer;
    std::streambuf* _cout_buffer;

   public:
    StandardStreamRedirect(std::streambuf* input, std::streambuf* output)
        : _cin_buffer(std::cin.rdbuf()), _cout_buffer(std::cout.rdbuf()) {
        std::cout.flush();
        std::cin.rdbuf(input);
        std::cout.rdbuf(output);
        std::cin.clear();
        std::cout.clear();
    }

    StandardStreamRedirect(const StandardStreamRedirect&) = delete;
    StandardStreamRedirect& operator=(const StandardStreamRedirect&) = delete;

    ~StandardStreamRedirect() {
        std::cout.flush();
        std::cin.rdbuf(_cin_buffer);
        std::cout.rdbuf(_cout_buffer);
        std::cin.clear();
        std::cout.clear();
    }
};

template <class Generator>
std::string generate_stream_input(Generator& generator, Random& random,
                                  int trial) {
    std::ostringstream output;
    if constexpr (std::invocable<Generator&, Random&, std::ostream&, int>) {
        std::invoke(generator, random, output, trial);
    } else {
        static_assert(std::invocable<Generator&, Random&, std::ostream&>);
        std::invoke(generator, random, output);
    }
    return output.str();
}

template <class Generator>
decltype(auto) generate_interactive_stream_input(Generator& generator,
                                                 Random& random,
                                                 std::ostream& output,
                                                 int trial) {
    if constexpr (std::invocable<Generator&, Random&, std::ostream&, int>) {
        return std::invoke(generator, random, output, trial);
    } else {
        static_assert(std::invocable<Generator&, Random&, std::ostream&>);
        return std::invoke(generator, random, output);
    }
}

template <class Solution>
std::string run_with_standard_streams(const std::string& input,
                                      Solution& solution) {
    std::istringstream input_stream(input);
    std::ostringstream output_stream;
    {
        StandardStreamRedirect redirect(input_stream.rdbuf(),
                                        output_stream.rdbuf());
        std::invoke(solution);
    }
    return output_stream.str();
}

inline std::string trim_line_breaks(std::string text) {
    while (!text.empty() &&
           (text.back() == '\n' || text.back() == '\r')) {
        text.pop_back();
    }
    return text;
}

template <class State, class QueryHandler>
class InteractiveStreamBuffer : public std::streambuf {
   private:
    State* _state;
    QueryHandler* _query_handler;
    std::stringbuf* _candidate_output;
    std::size_t _output_cursor = 0;
    int _query_limit;
    int _query_count = 0;
    std::string _input_chunk;
    InteractionTranscript _transcript;
    RandomTestFailure _failure = RandomTestFailure::none;
    std::exception_ptr _exception;

    void set_input_chunk(std::string text) {
        text.push_back('\n');
        _input_chunk = std::move(text);
        char* first = _input_chunk.data();
        setg(first, first, first + _input_chunk.size());
    }

    void fail(RandomTestFailure failure, std::string message) {
        _failure = failure;
        _transcript.failure_message = std::move(message);
        setg(nullptr, nullptr, nullptr);
    }

   protected:
    int_type underflow() override {
        if (gptr() != nullptr && gptr() < egptr()) {
            return traits_type::to_int_type(*gptr());
        }
        if (_failure != RandomTestFailure::none || _exception) {
            return traits_type::eof();
        }

        std::string all_output = _candidate_output->str();
        std::string query = all_output.substr(_output_cursor);
        _output_cursor = all_output.size();
        if (query.empty()) {
            fail(RandomTestFailure::invalid_query,
                 "solution requested input without writing a query");
            return traits_type::eof();
        }

        InteractionExchange exchange;
        exchange.query = trim_line_breaks(query);
        _transcript.exchanges.push_back(std::move(exchange));
        _query_count++;
        if (_query_limit < _query_count) {
            fail(RandomTestFailure::query_limit,
                 "attempted query " + std::to_string(_query_count) +
                     " with limit " + std::to_string(_query_limit));
            return traits_type::eof();
        }

        std::istringstream query_stream(query);
        std::ostringstream response_stream;
        try {
            std::invoke(*_query_handler, *_state, query_stream,
                        response_stream);
        } catch (const InteractionAbort& failure) {
            fail(failure.failure, failure.message);
            return traits_type::eof();
        } catch (...) {
            _exception = std::current_exception();
            return traits_type::eof();
        }

        std::string response = response_stream.str();
        InteractionExchange& recorded = _transcript.exchanges.back();
        recorded.response = trim_line_breaks(response);
        recorded.responded = true;
        set_input_chunk(std::move(response));
        return traits_type::to_int_type(*gptr());
    }

   public:
    InteractiveStreamBuffer(State& state, QueryHandler& query_handler,
                            std::stringbuf& candidate_output,
                            std::string initial_input, int query_limit)
        : _state(&state),
          _query_handler(&query_handler),
          _candidate_output(&candidate_output),
          _query_limit(query_limit) {
        set_input_chunk(std::move(initial_input));
    }

    void finish() {
        std::string all_output = _candidate_output->str();
        _transcript.answer = all_output.substr(_output_cursor);
        _transcript.answered = true;
    }

    RandomTestFailure failure() const {
        return _failure;
    }

    int query_count() const {
        return _query_count;
    }

    const InteractionTranscript& transcript() const {
        return _transcript;
    }

    const std::exception_ptr& exception() const {
        return _exception;
    }
};

template <class Solver, class Input, class Interaction>
decltype(auto) invoke_interactive_solver(Solver& solver, const Input& input,
                                         Interaction& interaction) {
    if constexpr (std::invocable<Solver&, const Input&, Interaction&>) {
        return std::invoke(solver, input, interaction);
    } else {
        static_assert(std::invocable<Solver&, Interaction&>);
        return std::invoke(solver, interaction);
    }
}

}  // namespace random_testing_detail

template <class Input, class State>
struct InteractiveTestCase {
    Input input;
    State state;
};

template <class Input, class State>
auto interactive_test_case(Input&& input, State&& state) {
    return InteractiveTestCase<std::remove_cvref_t<Input>,
                               std::remove_cvref_t<State>>{
        std::forward<Input>(input), std::forward<State>(state)};
}

// Call this from a query handler when the candidate violates the protocol.
[[noreturn]] inline void reject_query(std::string message = {}) {
    throw random_testing_detail::InteractionAbort{
        RandomTestFailure::invalid_query, std::move(message)};
}

template <class State, class QueryHandler>
class RandomInteraction {
   private:
    State* _state;
    QueryHandler* _query_handler;
    int _query_limit;
    int _query_count = 0;
    InteractionTranscript _transcript;

   public:
    RandomInteraction(State& state, QueryHandler& query_handler,
                      int query_limit)
        : _state(&state),
          _query_handler(&query_handler),
          _query_limit(query_limit) {}

    RandomInteraction(const RandomInteraction&) = delete;
    RandomInteraction& operator=(const RandomInteraction&) = delete;
    RandomInteraction(RandomInteraction&&) = delete;
    RandomInteraction& operator=(RandomInteraction&&) = delete;

    template <class Query>
    auto ask(Query&& query) {
        using Reply = std::remove_cvref_t<std::invoke_result_t<
            QueryHandler&, State&, Query>>;
        static_assert(!std::is_void_v<Reply>);

        InteractionExchange exchange;
        exchange.query = random_testing_detail::value_to_string(query);
        _transcript.exchanges.push_back(std::move(exchange));
        _query_count++;
        if (_query_limit < _query_count) {
            throw random_testing_detail::InteractionAbort{
                RandomTestFailure::query_limit,
                "attempted query " + std::to_string(_query_count) +
                    " with limit " + std::to_string(_query_limit)};
        }

        Reply reply = std::invoke(*_query_handler, *_state,
                                  std::forward<Query>(query));
        InteractionExchange& recorded = _transcript.exchanges.back();
        recorded.response = random_testing_detail::value_to_string(reply);
        recorded.responded = true;
        return reply;
    }

    int query_count() const {
        return _query_count;
    }

    const InteractionTranscript& transcript() const {
        return _transcript;
    }

    template <class Answer>
    void record_answer(const Answer& answer) {
        _transcript.answer =
            random_testing_detail::value_to_string(answer);
        _transcript.answered = true;
    }

    void record_failure(std::string message) {
        _transcript.failure_message = std::move(message);
    }
};

struct PrintRandomTestFailure {
    template <class Case, class Expected, class Actual>
    void operator()(const Case& test_case, const Expected& expected,
                    const Actual& actual, int trial,
                    std::uint64_t seed) const {
        std::cerr << "random test failed: seed=" << seed
                  << " trial=" << trial << '\n';
        std::cerr << "input: ";
        random_testing_detail::print_value(std::cerr, test_case);
        std::cerr << "\nexpected: ";
        random_testing_detail::print_value(std::cerr, expected);
        std::cerr << "\nactual: ";
        random_testing_detail::print_value(std::cerr, actual);
        std::cerr << '\n';
    }
};

struct PrintConstructiveTestFailure {
    template <class Case, class Answer>
    void operator()(const Case& test_case, const Answer& answer, int trial,
                    std::uint64_t seed) const {
        std::cerr << "constructive random test failed: seed=" << seed
                  << " trial=" << trial << '\n';
        std::cerr << "input: ";
        random_testing_detail::print_value(std::cerr, test_case);
        std::cerr << "\noutput: ";
        random_testing_detail::print_value(std::cerr, answer);
        std::cerr << '\n';
    }
};

struct PrintStreamTestFailure {
    void operator()(const std::string& input, const std::string& output,
                    int trial, std::uint64_t seed) const {
        std::cerr << "stream random test failed: seed=" << seed
                  << " trial=" << trial << "\ninput:\n"
                  << input;
        if (input.empty() || input.back() != '\n') std::cerr << '\n';
        std::cerr << "output:\n" << output;
        if (output.empty() || output.back() != '\n') std::cerr << '\n';
    }
};

struct PrintInteractiveTestFailure {
    template <class Input, class State>
    void operator()(const InteractiveTestCase<Input, State>& test_case,
                    const InteractionTranscript& transcript, int trial,
                    std::uint64_t seed,
                    RandomTestFailure failure) const {
        std::cerr << "interactive random test failed: seed=" << seed
                  << " trial=" << trial
                  << " reason=" << random_test_failure_name(failure) << '\n';
        std::cerr << "input: ";
        random_testing_detail::print_value(std::cerr, test_case.input);
        std::cerr << "\njudge state: ";
        random_testing_detail::print_value(std::cerr, test_case.state);
        std::cerr << '\n';
        for (int index = 0; index < int(transcript.exchanges.size()); index++) {
            const InteractionExchange& exchange = transcript.exchanges[index];
            std::cerr << "query " << index + 1 << ": " << exchange.query;
            if (exchange.responded) {
                std::cerr << " -> " << exchange.response;
            } else {
                std::cerr << " -> <no response>";
            }
            std::cerr << '\n';
        }
        if (transcript.answered) {
            std::cerr << "answer: " << transcript.answer << '\n';
        }
        if (!transcript.failure_message.empty()) {
            std::cerr << "message: " << transcript.failure_message << '\n';
        }
    }
};

struct PrintInteractiveStreamTestFailure {
    template <class State>
    void operator()(const std::string& input, const State& state,
                    const InteractionTranscript& transcript, int trial,
                    std::uint64_t seed,
                    RandomTestFailure failure) const {
        std::cerr << "interactive stream random test failed: seed=" << seed
                  << " trial=" << trial
                  << " reason=" << random_test_failure_name(failure)
                  << "\ninput:\n"
                  << input;
        if (input.empty() || input.back() != '\n') std::cerr << '\n';
        std::cerr << "judge state: ";
        random_testing_detail::print_value(std::cerr, state);
        std::cerr << '\n';
        for (int index = 0; index < int(transcript.exchanges.size()); index++) {
            const InteractionExchange& exchange = transcript.exchanges[index];
            std::cerr << "query " << index + 1 << ": " << exchange.query;
            if (exchange.responded) {
                std::cerr << " -> " << exchange.response;
            } else {
                std::cerr << " -> <no response>";
            }
            std::cerr << '\n';
        }
        if (transcript.answered) {
            std::cerr << "answer: " << transcript.answer;
            if (transcript.answer.empty() || transcript.answer.back() != '\n') {
                std::cerr << '\n';
            }
        }
        if (!transcript.failure_message.empty()) {
            std::cerr << "message: " << transcript.failure_message << '\n';
        }
    }
};

// Runs a property returning bool for every generated trial.
// The property may accept (Random&) or (Random&, int trial).
template <class Property>
RandomTestResult random_test(RandomTestConfig config, Property property) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);
    for (int trial = 0; trial < config.trials; trial++) {
        static_assert(std::convertible_to<
                      decltype(random_testing_detail::invoke_with_trial(
                          property, random, trial)),
                      bool>);
        bool passed = bool(
            random_testing_detail::invoke_with_trial(property, random, trial));
        if (!passed) {
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::property);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Property>
RandomTestResult random_test(Property property) {
    return random_test(RandomTestConfig(), std::move(property));
}

// Generates a case, runs an optimized solver and an oracle on separate copies,
// and compares their results. Stops at the first mismatch.
//
// generator: (Random&) or (Random&, int trial) -> Case
// solver/oracle: (Case&) -> result
// on_failure: (case, expected, actual, trial, seed) -> void
template <class Generator, class Solver, class Oracle,
          class OnFailure = IgnoreRandomTestFailure,
          class Equal = std::equal_to<>>
RandomTestResult compare_randomly(RandomTestConfig config, Generator generator,
                                  Solver solver, Oracle oracle,
                                  OnFailure on_failure = {}, Equal equal = {}) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        auto test_case =
            random_testing_detail::invoke_with_trial(generator, random, trial);
        using Case = std::remove_cvref_t<decltype(test_case)>;
        static_assert(std::copy_constructible<Case>);

        Case actual_input = test_case;
        Case expected_input = test_case;
        decltype(auto) actual = std::invoke(solver, actual_input);
        decltype(auto) expected = std::invoke(oracle, expected_input);
        if (!bool(std::invoke(equal, actual, expected))) {
            std::invoke(on_failure, test_case, expected, actual, trial,
                        config.seed);
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::mismatch);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solver, class Oracle>
RandomTestResult compare_randomly(Generator generator, Solver solver,
                                  Oracle oracle) {
    return compare_randomly(RandomTestConfig(), std::move(generator),
                            std::move(solver), std::move(oracle));
}

// Generates an input, runs a constructive solver, and validates its output.
// validator: (const Case&, const Answer&) -> bool
template <class Generator, class Solver, class Validator,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_constructively(RandomTestConfig config,
                                     Generator generator, Solver solver,
                                     Validator validator,
                                     OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        auto test_case =
            random_testing_detail::invoke_with_trial(generator, random, trial);
        using Case = std::remove_cvref_t<decltype(test_case)>;
        static_assert(std::copy_constructible<Case>);
        Case solver_input = test_case;
        auto answer = std::invoke(solver, solver_input);
        if (!bool(std::invoke(validator, std::as_const(test_case),
                              std::as_const(answer)))) {
            std::invoke(on_failure, std::as_const(test_case),
                        std::as_const(answer), trial, config.seed);
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::rejected_output);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solver, class Validator>
RandomTestResult test_constructively(Generator generator, Solver solver,
                                     Validator validator) {
    return test_constructively(RandomTestConfig(), std::move(generator),
                               std::move(solver), std::move(validator));
}

// Runs an ordinary solution that reads std::cin and writes std::cout.
// generator: (Random&, ostream&) or (Random&, ostream&, trial) -> void
// checker: (istream& generated_input, istream& candidate_output) -> bool
template <class Generator, class Solution, class Checker,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_streams(RandomTestConfig config, Generator generator,
                              Solution solution, Checker checker,
                              OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        std::string input = random_testing_detail::generate_stream_input(
            generator, random, trial);
        std::string output =
            random_testing_detail::run_with_standard_streams(input, solution);
        std::istringstream input_stream(input);
        std::istringstream output_stream(output);
        if (!bool(std::invoke(checker, input_stream, output_stream))) {
            std::invoke(on_failure, std::as_const(input),
                        std::as_const(output), trial, config.seed);
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::rejected_output);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solution, class Checker>
RandomTestResult test_streams(Generator generator, Solution solution,
                              Checker checker) {
    return test_streams(RandomTestConfig(), std::move(generator),
                        std::move(solution), std::move(checker));
}

// generator: (Random&) or (Random&, trial) -> InteractiveTestCase<Input, State>
// solver: (const Input&, interaction) or (interaction) -> Answer
// query_handler: (State&, Query) -> Reply
// validator: (const Input&, const State&, const Answer&) -> bool
template <class Generator, class Solver, class QueryHandler, class Validator,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_interactively(RandomTestConfig config, int query_limit,
                                    Generator generator, Solver solver,
                                    QueryHandler query_handler,
                                    Validator validator,
                                    OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    assert(0 <= query_limit);
    if (config.trials < 0) config.trials = 0;
    if (query_limit < 0) query_limit = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        auto test_case =
            random_testing_detail::invoke_with_trial(generator, random, trial);
        using State = std::remove_cvref_t<decltype(test_case.state)>;
        RandomInteraction<State, QueryHandler> interaction(
            test_case.state, query_handler, query_limit);

        try {
            auto answer = random_testing_detail::invoke_interactive_solver(
                solver, std::as_const(test_case.input), interaction);
            interaction.record_answer(answer);
            if (!bool(std::invoke(validator, std::as_const(test_case.input),
                                  std::as_const(test_case.state),
                                  std::as_const(answer)))) {
                RandomTestResult result =
                    random_testing_detail::failure_result(
                        config, trial, RandomTestFailure::rejected_output,
                        interaction.query_count());
                std::invoke(on_failure, std::as_const(test_case),
                            interaction.transcript(), trial, config.seed,
                            result.failure);
                return result;
            }
        } catch (const random_testing_detail::InteractionAbort& failure) {
            interaction.record_failure(failure.message);
            RandomTestResult result = random_testing_detail::failure_result(
                config, trial, failure.failure, interaction.query_count());
            std::invoke(on_failure, std::as_const(test_case),
                        interaction.transcript(), trial, config.seed,
                        result.failure);
            return result;
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solver, class QueryHandler, class Validator>
RandomTestResult test_interactively(int query_limit, Generator generator,
                                    Solver solver, QueryHandler query_handler,
                                    Validator validator) {
    return test_interactively(RandomTestConfig(), query_limit,
                              std::move(generator), std::move(solver),
                              std::move(query_handler), std::move(validator));
}

// Runs an ordinary interactive solution using std::cin and std::cout.
// generator: (Random&, ostream&) or (Random&, ostream&, trial) -> JudgeState
// query_handler: (JudgeState&, istream& query, ostream& response) -> void
// checker: (istream& public_input, const JudgeState&,
//           istream& final_output) -> bool
template <class Generator, class Solution, class QueryHandler, class Checker,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_interactive_streams(
    RandomTestConfig config, int query_limit, Generator generator,
    Solution solution, QueryHandler query_handler, Checker checker,
    OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    assert(0 <= query_limit);
    if (config.trials < 0) config.trials = 0;
    if (query_limit < 0) query_limit = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        std::ostringstream generated_input;
        auto state =
            random_testing_detail::generate_interactive_stream_input(
                generator, random, generated_input, trial);
        std::string input = generated_input.str();
        std::stringbuf candidate_output(std::ios::out);
        using State = std::remove_cvref_t<decltype(state)>;
        random_testing_detail::InteractiveStreamBuffer<State, QueryHandler>
            input_buffer(state, query_handler, candidate_output, input,
                         query_limit);
        {
            random_testing_detail::StandardStreamRedirect redirect(
                &input_buffer, &candidate_output);
            std::invoke(solution);
        }
        input_buffer.finish();
        if (input_buffer.exception()) {
            std::rethrow_exception(input_buffer.exception());
        }

        RandomTestFailure failure = input_buffer.failure();
        if (failure != RandomTestFailure::none) {
            RandomTestResult result = random_testing_detail::failure_result(
                config, trial, failure, input_buffer.query_count());
            std::invoke(on_failure, std::as_const(input),
                        std::as_const(state), input_buffer.transcript(), trial,
                        config.seed, failure);
            return result;
        }

        std::istringstream input_stream(input);
        std::istringstream output_stream(input_buffer.transcript().answer);
        if (!bool(std::invoke(checker, input_stream, std::as_const(state),
                              output_stream))) {
            RandomTestResult result = random_testing_detail::failure_result(
                config, trial, RandomTestFailure::rejected_output,
                input_buffer.query_count());
            std::invoke(on_failure, std::as_const(input),
                        std::as_const(state), input_buffer.transcript(), trial,
                        config.seed, result.failure);
            return result;
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solution, class QueryHandler, class Checker>
RandomTestResult test_interactive_streams(
    int query_limit, Generator generator, Solution solution,
    QueryHandler query_handler, Checker checker) {
    return test_interactive_streams(
        RandomTestConfig(), query_limit, std::move(generator),
        std::move(solution), std::move(query_handler), std::move(checker));
}

// Short contest interface. Prints failure metadata and terminates on failure.
template <class Property>
RandomTestResult stress_test(Property property, int trials = 1000,
                             std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = random_test(config, std::move(property));
    if (!result) {
        std::cerr << "random test failed: seed=" << result.seed
                  << " trial=" << result.failed_trial << '\n';
        std::abort();
    }
    return result;
}

// Short optimized-versus-brute-force interface.
template <class Generator, class Solver, class Oracle>
requires(!std::integral<std::remove_cvref_t<Solver>> &&
         !std::integral<std::remove_cvref_t<Oracle>>)
RandomTestResult stress_test(Generator generator, Solver solver, Oracle oracle,
                             int trials = 1000,
                             std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = compare_randomly(
        config, std::move(generator), std::move(solver), std::move(oracle),
        PrintRandomTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solver, class Validator>
RandomTestResult constructive_stress_test(
    Generator generator, Solver solver, Validator validator,
    int trials = 1000, std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_constructively(
        config, std::move(generator), std::move(solver),
        std::move(validator), PrintConstructiveTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solution, class Checker>
RandomTestResult stream_stress_test(
    Generator generator, Solution solution, Checker checker,
    int trials = 1000, std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_streams(
        config, std::move(generator), std::move(solution),
        std::move(checker), PrintStreamTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solver, class QueryHandler, class Validator>
RandomTestResult interactive_stress_test(
    int query_limit, Generator generator, Solver solver,
    QueryHandler query_handler, Validator validator, int trials = 1000,
    std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_interactively(
        config, query_limit, std::move(generator), std::move(solver),
        std::move(query_handler), std::move(validator),
        PrintInteractiveTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solution, class QueryHandler, class Checker>
RandomTestResult interactive_stream_stress_test(
    int query_limit, Generator generator, Solution solution,
    QueryHandler query_handler, Checker checker, int trials = 1000,
    std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_interactive_streams(
        config, query_limit, std::move(generator), std::move(solution),
        std::move(query_handler), std::move(checker),
        PrintInteractiveStreamTestFailure());
    if (!result) std::abort();
    return result;
}

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_RANDOM_TESTING_HPP

#line 1 "utilities/random_testing.hpp"



#include <cassert>
#include <concepts>
#include <cstdint>
#include <cstdlib>
#include <exception>
#include <functional>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#line 1 "utilities/random.hpp"



#include <algorithm>
#line 6 "utilities/random.hpp"
#include <chrono>
#line 10 "utilities/random.hpp"
#include <numeric>
#include <queue>
#include <random>
#line 14 "utilities/random.hpp"
#include <string_view>
#line 17 "utilities/random.hpp"
#include <unordered_set>
#line 20 "utilities/random.hpp"

namespace m1une {
namespace utilities {

struct RandomGraphOptions {
    bool directed = false;
    bool allow_self_loops = false;
    bool allow_parallel_edges = false;
};

struct Random {
   private:
    std::mt19937_64 _engine;

    static unsigned long long chrono_seed() {
        return static_cast<unsigned long long>(
            std::chrono::steady_clock::now().time_since_epoch().count());
    }

    static std::uint64_t graph_edge_count(int vertex_count,
                                          const RandomGraphOptions& options) {
        std::uint64_t n = static_cast<unsigned int>(vertex_count);
        if (options.directed) {
            return options.allow_self_loops ? n * n : n * (n - 1);
        }
        return options.allow_self_loops ? n * (n + 1) / 2 : n * (n - 1) / 2;
    }

    static std::pair<int, int> decode_graph_edge(
        std::uint64_t index, int vertex_count,
        const RandomGraphOptions& options) {
        std::uint64_t n = static_cast<unsigned int>(vertex_count);
        if (options.directed) {
            std::uint64_t width = options.allow_self_loops ? n : n - 1;
            int from = int(index / width);
            int offset = int(index % width);
            int to = options.allow_self_loops || offset < from ? offset : offset + 1;
            return {from, to};
        }

        auto prefix = [&](std::uint64_t vertex) {
            if (options.allow_self_loops) {
                return vertex * (2 * n - vertex + 1) / 2;
            }
            return vertex * (2 * n - vertex - 1) / 2;
        };
        std::uint64_t low = 0;
        std::uint64_t high = n;
        while (low + 1 < high) {
            std::uint64_t middle = (low + high) / 2;
            if (prefix(middle) <= index) {
                low = middle;
            } else {
                high = middle;
            }
        }
        int from = int(low);
        int to = from + int(index - prefix(low)) +
                 (options.allow_self_loops ? 0 : 1);
        return {from, to};
    }

   public:
    Random() : _engine(chrono_seed()) {}
    explicit Random(unsigned long long seed) : _engine(seed) {}

    void seed(unsigned long long value) {
        _engine.seed(value);
    }

    std::mt19937_64& engine() {
        return _engine;
    }

    unsigned long long operator()() {
        return _engine();
    }

    long long uniform(long long l, long long r) {
        return std::uniform_int_distribution<long long>(l, r)(_engine);
    }

    unsigned long long uniform_unsigned(unsigned long long l, unsigned long long r) {
        return std::uniform_int_distribution<unsigned long long>(l, r)(_engine);
    }

    double real(double l = 0.0, double r = 1.0) {
        return std::uniform_real_distribution<double>(l, r)(_engine);
    }

    template <std::integral T>
    requires(!std::same_as<std::remove_cv_t<T>, bool>)
    std::vector<T> sequence(int size, T lower, T upper) {
        assert(0 <= size);
        assert(lower <= upper);
        if (size < 0 || upper < lower) return {};
        std::vector<T> result(size);
        if constexpr (std::signed_integral<T>) {
            std::uniform_int_distribution<long long> distribution(
                static_cast<long long>(lower), static_cast<long long>(upper));
            for (T& value : result) value = static_cast<T>(distribution(_engine));
        } else {
            std::uniform_int_distribution<unsigned long long> distribution(
                static_cast<unsigned long long>(lower),
                static_cast<unsigned long long>(upper));
            for (T& value : result) value = static_cast<T>(distribution(_engine));
        }
        return result;
    }

    std::string string(
        int length,
        std::string_view alphabet = "abcdefghijklmnopqrstuvwxyz") {
        assert(0 <= length);
        assert(length == 0 || !alphabet.empty());
        if (length < 0 || (0 < length && alphabet.empty())) return {};
        std::string result(length, '\0');
        for (char& character : result) {
            character = alphabet[uniform(0, int(alphabet.size()) - 1)];
        }
        return result;
    }

    std::vector<int> permutation(int size, int first = 0) {
        assert(0 <= size);
        if (size < 0) return {};
        std::vector<int> result(size);
        std::iota(result.begin(), result.end(), first);
        shuffle(result);
        return result;
    }

    // Returns the edges of a uniformly random labeled tree on [0, size).
    std::vector<std::pair<int, int>> tree(int size) {
        assert(0 <= size);
        if (size <= 1) return {};

        std::vector<int> prufer = sequence(size - 2, 0, size - 1);
        std::vector<int> degree(size, 1);
        for (int vertex : prufer) degree[vertex]++;
        std::priority_queue<int, std::vector<int>, std::greater<int>> leaves;
        for (int vertex = 0; vertex < size; vertex++) {
            if (degree[vertex] == 1) leaves.push(vertex);
        }

        std::vector<std::pair<int, int>> edges;
        edges.reserve(size - 1);
        for (int vertex : prufer) {
            int leaf = leaves.top();
            leaves.pop();
            edges.emplace_back(leaf, vertex);
            if (--degree[vertex] == 1) leaves.push(vertex);
        }
        int first = leaves.top();
        leaves.pop();
        edges.emplace_back(first, leaves.top());

        shuffle(edges);
        for (auto& [from, to] : edges) {
            if (uniform(0, 1)) std::swap(from, to);
        }
        return edges;
    }

    // Returns m random edges on [0, vertex_count). By default the result is
    // a simple undirected graph without self-loops.
    std::vector<std::pair<int, int>> graph(
        int vertex_count, int edge_count,
        RandomGraphOptions options = {}) {
        assert(0 <= vertex_count);
        assert(0 <= edge_count);
        if (vertex_count < 0 || edge_count < 0) return {};
        if (edge_count == 0) return {};
        assert(0 < vertex_count);
        if (vertex_count == 0) return {};
        if (!options.allow_self_loops) {
            assert(2 <= vertex_count || edge_count == 0);
            if (vertex_count < 2) return {};
        }

        std::vector<std::pair<int, int>> edges;
        edges.reserve(edge_count);
        if (options.allow_parallel_edges) {
            for (int edge = 0; edge < edge_count; edge++) {
                int from = int(uniform(0, vertex_count - 1));
                int to;
                if (options.allow_self_loops) {
                    to = int(uniform(0, vertex_count - 1));
                } else {
                    to = int(uniform(0, vertex_count - 2));
                    if (from <= to) to++;
                }
                if (!options.directed && to < from) std::swap(from, to);
                edges.emplace_back(from, to);
            }
            return edges;
        }

        std::uint64_t maximum = graph_edge_count(vertex_count, options);
        assert(static_cast<std::uint64_t>(edge_count) <= maximum);
        if (maximum < static_cast<std::uint64_t>(edge_count)) return {};

        std::unordered_set<std::uint64_t> selected;
        selected.reserve(static_cast<std::size_t>(edge_count) * 2 + 1);
        std::vector<std::uint64_t> indices;
        indices.reserve(edge_count);
        for (std::uint64_t current = maximum - edge_count;
             current < maximum; current++) {
            std::uint64_t candidate = uniform_unsigned(0, current);
            if (selected.contains(candidate)) candidate = current;
            selected.insert(candidate);
            indices.push_back(candidate);
        }
        for (std::uint64_t index : indices) {
            edges.push_back(decode_graph_edge(index, vertex_count, options));
        }
        return edges;
    }

    std::vector<std::pair<int, int>> directed_graph(
        int vertex_count, int edge_count,
        bool allow_self_loops = false) {
        RandomGraphOptions options;
        options.allow_self_loops = allow_self_loops;
        return directed_graph(vertex_count, edge_count, options);
    }

    std::vector<std::pair<int, int>> directed_graph(
        int vertex_count, int edge_count, RandomGraphOptions options) {
        options.directed = true;
        return graph(vertex_count, edge_count, options);
    }

    // Returns a directed acyclic graph. Vertices are randomly permuted before
    // every sampled edge is directed forward in that topological order.
    std::vector<std::pair<int, int>> dag(
        int vertex_count, int edge_count,
        RandomGraphOptions options = {}) {
        options.directed = false;
        options.allow_self_loops = false;
        std::vector<std::pair<int, int>> edges =
            graph(vertex_count, edge_count, options);
        std::vector<int> order = permutation(vertex_count);
        for (auto& [from, to] : edges) {
            from = order[from];
            to = order[to];
        }
        return edges;
    }

    template <std::integral Weight>
    requires(!std::same_as<std::remove_cv_t<Weight>, bool>)
    std::vector<std::tuple<int, int, Weight>> weighted_tree(
        int size, Weight lower, Weight upper) {
        std::vector<std::pair<int, int>> edges = tree(size);
        std::vector<Weight> weights = sequence(int(edges.size()), lower, upper);
        std::vector<std::tuple<int, int, Weight>> result;
        result.reserve(edges.size());
        for (int index = 0; index < int(edges.size()); index++) {
            result.emplace_back(edges[index].first, edges[index].second,
                                weights[index]);
        }
        return result;
    }

    template <std::integral Weight>
    requires(!std::same_as<std::remove_cv_t<Weight>, bool>)
    std::vector<std::tuple<int, int, Weight>> weighted_graph(
        int vertex_count, int edge_count, Weight lower, Weight upper,
        RandomGraphOptions options = {}) {
        std::vector<std::pair<int, int>> edges =
            graph(vertex_count, edge_count, options);
        std::vector<Weight> weights = sequence(int(edges.size()), lower, upper);
        std::vector<std::tuple<int, int, Weight>> result;
        result.reserve(edges.size());
        for (int index = 0; index < int(edges.size()); index++) {
            result.emplace_back(edges[index].first, edges[index].second,
                                weights[index]);
        }
        return result;
    }

    template <std::integral Weight>
    requires(!std::same_as<std::remove_cv_t<Weight>, bool>)
    std::vector<std::tuple<int, int, Weight>> weighted_directed_graph(
        int vertex_count, int edge_count, Weight lower, Weight upper,
        bool allow_self_loops = false) {
        RandomGraphOptions options;
        options.allow_self_loops = allow_self_loops;
        return weighted_directed_graph(vertex_count, edge_count, lower, upper,
                                       options);
    }

    template <std::integral Weight>
    requires(!std::same_as<std::remove_cv_t<Weight>, bool>)
    std::vector<std::tuple<int, int, Weight>> weighted_directed_graph(
        int vertex_count, int edge_count, Weight lower, Weight upper,
        RandomGraphOptions options) {
        options.directed = true;
        return weighted_graph(vertex_count, edge_count, lower, upper, options);
    }

    template <std::integral Weight>
    requires(!std::same_as<std::remove_cv_t<Weight>, bool>)
    std::vector<std::tuple<int, int, Weight>> weighted_dag(
        int vertex_count, int edge_count, Weight lower, Weight upper,
        RandomGraphOptions options = {}) {
        std::vector<std::pair<int, int>> edges =
            dag(vertex_count, edge_count, options);
        std::vector<Weight> weights = sequence(int(edges.size()), lower, upper);
        std::vector<std::tuple<int, int, Weight>> result;
        result.reserve(edges.size());
        for (int index = 0; index < int(edges.size()); index++) {
            result.emplace_back(edges[index].first, edges[index].second,
                                weights[index]);
        }
        return result;
    }

    template <typename T>
    void shuffle(std::vector<T>& v) {
        std::shuffle(v.begin(), v.end(), _engine);
    }

    template <typename Iterator>
    void shuffle(Iterator first, Iterator last) {
        std::shuffle(first, last, _engine);
    }

    template <typename T>
    const T& choice(const std::vector<T>& v) {
        return v[uniform(0, static_cast<long long>(v.size()) - 1)];
    }
};

}  // namespace utilities
}  // namespace m1une


#line 20 "utilities/random_testing.hpp"

namespace m1une {
namespace utilities {

inline constexpr std::uint64_t default_random_test_seed =
    0x243f6a8885a308d3ULL;

struct RandomTestConfig {
    int trials = 1000;
    std::uint64_t seed = default_random_test_seed;
};

enum class RandomTestFailure {
    none,
    property,
    mismatch,
    rejected_output,
    query_limit,
    invalid_query,
};

inline const char* random_test_failure_name(RandomTestFailure failure) {
    switch (failure) {
        case RandomTestFailure::none:
            return "none";
        case RandomTestFailure::property:
            return "property";
        case RandomTestFailure::mismatch:
            return "mismatch";
        case RandomTestFailure::rejected_output:
            return "rejected output";
        case RandomTestFailure::query_limit:
            return "query limit exceeded";
        case RandomTestFailure::invalid_query:
            return "invalid query";
    }
    return "unknown";
}

struct RandomTestResult {
    std::uint64_t seed = 0;
    int requested_trials = 0;
    int completed_trials = 0;
    int failed_trial = -1;
    RandomTestFailure failure = RandomTestFailure::none;
    int query_count = -1;

    bool passed() const {
        return failed_trial == -1;
    }

    explicit operator bool() const {
        return passed();
    }
};

struct IgnoreRandomTestFailure {
    template <class... Args>
    void operator()(Args&&...) const {}
};

struct InteractionExchange {
    std::string query;
    std::string response;
    bool responded = false;
};

struct InteractionTranscript {
    std::vector<InteractionExchange> exchanges;
    std::string answer;
    bool answered = false;
    std::string failure_message;
};

namespace random_testing_detail {

template <class T>
void print_value(std::ostream& output, const T& value) {
    if constexpr (requires { output << value; }) {
        output << value;
    } else if constexpr (requires {
                             typename std::tuple_size<
                                 std::remove_cvref_t<T>>::type;
                         }) {
        output << '(';
        int index = 0;
        std::apply(
            [&](const auto&... elements) {
                ((output << (index++ == 0 ? "" : ", "),
                  print_value(output, elements)),
                 ...);
            },
            value);
        output << ')';
    } else if constexpr (requires { std::begin(value); std::end(value); }) {
        output << '[';
        bool first = true;
        for (const auto& element : value) {
            if (!first) output << ", ";
            first = false;
            print_value(output, element);
        }
        output << ']';
    } else {
        output << "<unprintable>";
    }
}

template <class Function>
decltype(auto) invoke_with_trial(Function& function, Random& random, int trial) {
    if constexpr (std::invocable<Function&, Random&, int>) {
        return std::invoke(function, random, trial);
    } else {
        static_assert(std::invocable<Function&, Random&>);
        return std::invoke(function, random);
    }
}

inline RandomTestResult success_result(const RandomTestConfig& config) {
    RandomTestResult result;
    result.seed = config.seed;
    result.requested_trials = config.trials;
    result.completed_trials = config.trials;
    return result;
}

inline RandomTestResult failure_result(const RandomTestConfig& config,
                                       int failed_trial,
                                       RandomTestFailure failure,
                                       int query_count = -1) {
    RandomTestResult result;
    result.seed = config.seed;
    result.requested_trials = config.trials;
    result.completed_trials = failed_trial;
    result.failed_trial = failed_trial;
    result.failure = failure;
    result.query_count = query_count;
    return result;
}

template <class T>
std::string value_to_string(const T& value) {
    std::ostringstream output;
    print_value(output, value);
    return output.str();
}

struct InteractionAbort {
    RandomTestFailure failure;
    std::string message;
};

class StandardStreamRedirect {
   private:
    std::streambuf* _cin_buffer;
    std::streambuf* _cout_buffer;

   public:
    StandardStreamRedirect(std::streambuf* input, std::streambuf* output)
        : _cin_buffer(std::cin.rdbuf()), _cout_buffer(std::cout.rdbuf()) {
        std::cout.flush();
        std::cin.rdbuf(input);
        std::cout.rdbuf(output);
        std::cin.clear();
        std::cout.clear();
    }

    StandardStreamRedirect(const StandardStreamRedirect&) = delete;
    StandardStreamRedirect& operator=(const StandardStreamRedirect&) = delete;

    ~StandardStreamRedirect() {
        std::cout.flush();
        std::cin.rdbuf(_cin_buffer);
        std::cout.rdbuf(_cout_buffer);
        std::cin.clear();
        std::cout.clear();
    }
};

template <class Generator>
std::string generate_stream_input(Generator& generator, Random& random,
                                  int trial) {
    std::ostringstream output;
    if constexpr (std::invocable<Generator&, Random&, std::ostream&, int>) {
        std::invoke(generator, random, output, trial);
    } else {
        static_assert(std::invocable<Generator&, Random&, std::ostream&>);
        std::invoke(generator, random, output);
    }
    return output.str();
}

template <class Generator>
decltype(auto) generate_interactive_stream_input(Generator& generator,
                                                 Random& random,
                                                 std::ostream& output,
                                                 int trial) {
    if constexpr (std::invocable<Generator&, Random&, std::ostream&, int>) {
        return std::invoke(generator, random, output, trial);
    } else {
        static_assert(std::invocable<Generator&, Random&, std::ostream&>);
        return std::invoke(generator, random, output);
    }
}

template <class Solution>
std::string run_with_standard_streams(const std::string& input,
                                      Solution& solution) {
    std::istringstream input_stream(input);
    std::ostringstream output_stream;
    {
        StandardStreamRedirect redirect(input_stream.rdbuf(),
                                        output_stream.rdbuf());
        std::invoke(solution);
    }
    return output_stream.str();
}

inline std::string trim_line_breaks(std::string text) {
    while (!text.empty() &&
           (text.back() == '\n' || text.back() == '\r')) {
        text.pop_back();
    }
    return text;
}

template <class State, class QueryHandler>
class InteractiveStreamBuffer : public std::streambuf {
   private:
    State* _state;
    QueryHandler* _query_handler;
    std::stringbuf* _candidate_output;
    std::size_t _output_cursor = 0;
    int _query_limit;
    int _query_count = 0;
    std::string _input_chunk;
    InteractionTranscript _transcript;
    RandomTestFailure _failure = RandomTestFailure::none;
    std::exception_ptr _exception;

    void set_input_chunk(std::string text) {
        text.push_back('\n');
        _input_chunk = std::move(text);
        char* first = _input_chunk.data();
        setg(first, first, first + _input_chunk.size());
    }

    void fail(RandomTestFailure failure, std::string message) {
        _failure = failure;
        _transcript.failure_message = std::move(message);
        setg(nullptr, nullptr, nullptr);
    }

   protected:
    int_type underflow() override {
        if (gptr() != nullptr && gptr() < egptr()) {
            return traits_type::to_int_type(*gptr());
        }
        if (_failure != RandomTestFailure::none || _exception) {
            return traits_type::eof();
        }

        std::string all_output = _candidate_output->str();
        std::string query = all_output.substr(_output_cursor);
        _output_cursor = all_output.size();
        if (query.empty()) {
            fail(RandomTestFailure::invalid_query,
                 "solution requested input without writing a query");
            return traits_type::eof();
        }

        InteractionExchange exchange;
        exchange.query = trim_line_breaks(query);
        _transcript.exchanges.push_back(std::move(exchange));
        _query_count++;
        if (_query_limit < _query_count) {
            fail(RandomTestFailure::query_limit,
                 "attempted query " + std::to_string(_query_count) +
                     " with limit " + std::to_string(_query_limit));
            return traits_type::eof();
        }

        std::istringstream query_stream(query);
        std::ostringstream response_stream;
        try {
            std::invoke(*_query_handler, *_state, query_stream,
                        response_stream);
        } catch (const InteractionAbort& failure) {
            fail(failure.failure, failure.message);
            return traits_type::eof();
        } catch (...) {
            _exception = std::current_exception();
            return traits_type::eof();
        }

        std::string response = response_stream.str();
        InteractionExchange& recorded = _transcript.exchanges.back();
        recorded.response = trim_line_breaks(response);
        recorded.responded = true;
        set_input_chunk(std::move(response));
        return traits_type::to_int_type(*gptr());
    }

   public:
    InteractiveStreamBuffer(State& state, QueryHandler& query_handler,
                            std::stringbuf& candidate_output,
                            std::string initial_input, int query_limit)
        : _state(&state),
          _query_handler(&query_handler),
          _candidate_output(&candidate_output),
          _query_limit(query_limit) {
        set_input_chunk(std::move(initial_input));
    }

    void finish() {
        std::string all_output = _candidate_output->str();
        _transcript.answer = all_output.substr(_output_cursor);
        _transcript.answered = true;
    }

    RandomTestFailure failure() const {
        return _failure;
    }

    int query_count() const {
        return _query_count;
    }

    const InteractionTranscript& transcript() const {
        return _transcript;
    }

    const std::exception_ptr& exception() const {
        return _exception;
    }
};

template <class Solver, class Input, class Interaction>
decltype(auto) invoke_interactive_solver(Solver& solver, const Input& input,
                                         Interaction& interaction) {
    if constexpr (std::invocable<Solver&, const Input&, Interaction&>) {
        return std::invoke(solver, input, interaction);
    } else {
        static_assert(std::invocable<Solver&, Interaction&>);
        return std::invoke(solver, interaction);
    }
}

}  // namespace random_testing_detail

template <class Input, class State>
struct InteractiveTestCase {
    Input input;
    State state;
};

template <class Input, class State>
auto interactive_test_case(Input&& input, State&& state) {
    return InteractiveTestCase<std::remove_cvref_t<Input>,
                               std::remove_cvref_t<State>>{
        std::forward<Input>(input), std::forward<State>(state)};
}

// Call this from a query handler when the candidate violates the protocol.
[[noreturn]] inline void reject_query(std::string message = {}) {
    throw random_testing_detail::InteractionAbort{
        RandomTestFailure::invalid_query, std::move(message)};
}

template <class State, class QueryHandler>
class RandomInteraction {
   private:
    State* _state;
    QueryHandler* _query_handler;
    int _query_limit;
    int _query_count = 0;
    InteractionTranscript _transcript;

   public:
    RandomInteraction(State& state, QueryHandler& query_handler,
                      int query_limit)
        : _state(&state),
          _query_handler(&query_handler),
          _query_limit(query_limit) {}

    RandomInteraction(const RandomInteraction&) = delete;
    RandomInteraction& operator=(const RandomInteraction&) = delete;
    RandomInteraction(RandomInteraction&&) = delete;
    RandomInteraction& operator=(RandomInteraction&&) = delete;

    template <class Query>
    auto ask(Query&& query) {
        using Reply = std::remove_cvref_t<std::invoke_result_t<
            QueryHandler&, State&, Query>>;
        static_assert(!std::is_void_v<Reply>);

        InteractionExchange exchange;
        exchange.query = random_testing_detail::value_to_string(query);
        _transcript.exchanges.push_back(std::move(exchange));
        _query_count++;
        if (_query_limit < _query_count) {
            throw random_testing_detail::InteractionAbort{
                RandomTestFailure::query_limit,
                "attempted query " + std::to_string(_query_count) +
                    " with limit " + std::to_string(_query_limit)};
        }

        Reply reply = std::invoke(*_query_handler, *_state,
                                  std::forward<Query>(query));
        InteractionExchange& recorded = _transcript.exchanges.back();
        recorded.response = random_testing_detail::value_to_string(reply);
        recorded.responded = true;
        return reply;
    }

    int query_count() const {
        return _query_count;
    }

    const InteractionTranscript& transcript() const {
        return _transcript;
    }

    template <class Answer>
    void record_answer(const Answer& answer) {
        _transcript.answer =
            random_testing_detail::value_to_string(answer);
        _transcript.answered = true;
    }

    void record_failure(std::string message) {
        _transcript.failure_message = std::move(message);
    }
};

struct PrintRandomTestFailure {
    template <class Case, class Expected, class Actual>
    void operator()(const Case& test_case, const Expected& expected,
                    const Actual& actual, int trial,
                    std::uint64_t seed) const {
        std::cerr << "random test failed: seed=" << seed
                  << " trial=" << trial << '\n';
        std::cerr << "input: ";
        random_testing_detail::print_value(std::cerr, test_case);
        std::cerr << "\nexpected: ";
        random_testing_detail::print_value(std::cerr, expected);
        std::cerr << "\nactual: ";
        random_testing_detail::print_value(std::cerr, actual);
        std::cerr << '\n';
    }
};

struct PrintConstructiveTestFailure {
    template <class Case, class Answer>
    void operator()(const Case& test_case, const Answer& answer, int trial,
                    std::uint64_t seed) const {
        std::cerr << "constructive random test failed: seed=" << seed
                  << " trial=" << trial << '\n';
        std::cerr << "input: ";
        random_testing_detail::print_value(std::cerr, test_case);
        std::cerr << "\noutput: ";
        random_testing_detail::print_value(std::cerr, answer);
        std::cerr << '\n';
    }
};

struct PrintStreamTestFailure {
    void operator()(const std::string& input, const std::string& output,
                    int trial, std::uint64_t seed) const {
        std::cerr << "stream random test failed: seed=" << seed
                  << " trial=" << trial << "\ninput:\n"
                  << input;
        if (input.empty() || input.back() != '\n') std::cerr << '\n';
        std::cerr << "output:\n" << output;
        if (output.empty() || output.back() != '\n') std::cerr << '\n';
    }
};

struct PrintInteractiveTestFailure {
    template <class Input, class State>
    void operator()(const InteractiveTestCase<Input, State>& test_case,
                    const InteractionTranscript& transcript, int trial,
                    std::uint64_t seed,
                    RandomTestFailure failure) const {
        std::cerr << "interactive random test failed: seed=" << seed
                  << " trial=" << trial
                  << " reason=" << random_test_failure_name(failure) << '\n';
        std::cerr << "input: ";
        random_testing_detail::print_value(std::cerr, test_case.input);
        std::cerr << "\njudge state: ";
        random_testing_detail::print_value(std::cerr, test_case.state);
        std::cerr << '\n';
        for (int index = 0; index < int(transcript.exchanges.size()); index++) {
            const InteractionExchange& exchange = transcript.exchanges[index];
            std::cerr << "query " << index + 1 << ": " << exchange.query;
            if (exchange.responded) {
                std::cerr << " -> " << exchange.response;
            } else {
                std::cerr << " -> <no response>";
            }
            std::cerr << '\n';
        }
        if (transcript.answered) {
            std::cerr << "answer: " << transcript.answer << '\n';
        }
        if (!transcript.failure_message.empty()) {
            std::cerr << "message: " << transcript.failure_message << '\n';
        }
    }
};

struct PrintInteractiveStreamTestFailure {
    template <class State>
    void operator()(const std::string& input, const State& state,
                    const InteractionTranscript& transcript, int trial,
                    std::uint64_t seed,
                    RandomTestFailure failure) const {
        std::cerr << "interactive stream random test failed: seed=" << seed
                  << " trial=" << trial
                  << " reason=" << random_test_failure_name(failure)
                  << "\ninput:\n"
                  << input;
        if (input.empty() || input.back() != '\n') std::cerr << '\n';
        std::cerr << "judge state: ";
        random_testing_detail::print_value(std::cerr, state);
        std::cerr << '\n';
        for (int index = 0; index < int(transcript.exchanges.size()); index++) {
            const InteractionExchange& exchange = transcript.exchanges[index];
            std::cerr << "query " << index + 1 << ": " << exchange.query;
            if (exchange.responded) {
                std::cerr << " -> " << exchange.response;
            } else {
                std::cerr << " -> <no response>";
            }
            std::cerr << '\n';
        }
        if (transcript.answered) {
            std::cerr << "answer: " << transcript.answer;
            if (transcript.answer.empty() || transcript.answer.back() != '\n') {
                std::cerr << '\n';
            }
        }
        if (!transcript.failure_message.empty()) {
            std::cerr << "message: " << transcript.failure_message << '\n';
        }
    }
};

// Runs a property returning bool for every generated trial.
// The property may accept (Random&) or (Random&, int trial).
template <class Property>
RandomTestResult random_test(RandomTestConfig config, Property property) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);
    for (int trial = 0; trial < config.trials; trial++) {
        static_assert(std::convertible_to<
                      decltype(random_testing_detail::invoke_with_trial(
                          property, random, trial)),
                      bool>);
        bool passed = bool(
            random_testing_detail::invoke_with_trial(property, random, trial));
        if (!passed) {
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::property);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Property>
RandomTestResult random_test(Property property) {
    return random_test(RandomTestConfig(), std::move(property));
}

// Generates a case, runs an optimized solver and an oracle on separate copies,
// and compares their results. Stops at the first mismatch.
//
// generator: (Random&) or (Random&, int trial) -> Case
// solver/oracle: (Case&) -> result
// on_failure: (case, expected, actual, trial, seed) -> void
template <class Generator, class Solver, class Oracle,
          class OnFailure = IgnoreRandomTestFailure,
          class Equal = std::equal_to<>>
RandomTestResult compare_randomly(RandomTestConfig config, Generator generator,
                                  Solver solver, Oracle oracle,
                                  OnFailure on_failure = {}, Equal equal = {}) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        auto test_case =
            random_testing_detail::invoke_with_trial(generator, random, trial);
        using Case = std::remove_cvref_t<decltype(test_case)>;
        static_assert(std::copy_constructible<Case>);

        Case actual_input = test_case;
        Case expected_input = test_case;
        decltype(auto) actual = std::invoke(solver, actual_input);
        decltype(auto) expected = std::invoke(oracle, expected_input);
        if (!bool(std::invoke(equal, actual, expected))) {
            std::invoke(on_failure, test_case, expected, actual, trial,
                        config.seed);
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::mismatch);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solver, class Oracle>
RandomTestResult compare_randomly(Generator generator, Solver solver,
                                  Oracle oracle) {
    return compare_randomly(RandomTestConfig(), std::move(generator),
                            std::move(solver), std::move(oracle));
}

// Generates an input, runs a constructive solver, and validates its output.
// validator: (const Case&, const Answer&) -> bool
template <class Generator, class Solver, class Validator,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_constructively(RandomTestConfig config,
                                     Generator generator, Solver solver,
                                     Validator validator,
                                     OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        auto test_case =
            random_testing_detail::invoke_with_trial(generator, random, trial);
        using Case = std::remove_cvref_t<decltype(test_case)>;
        static_assert(std::copy_constructible<Case>);
        Case solver_input = test_case;
        auto answer = std::invoke(solver, solver_input);
        if (!bool(std::invoke(validator, std::as_const(test_case),
                              std::as_const(answer)))) {
            std::invoke(on_failure, std::as_const(test_case),
                        std::as_const(answer), trial, config.seed);
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::rejected_output);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solver, class Validator>
RandomTestResult test_constructively(Generator generator, Solver solver,
                                     Validator validator) {
    return test_constructively(RandomTestConfig(), std::move(generator),
                               std::move(solver), std::move(validator));
}

// Runs an ordinary solution that reads std::cin and writes std::cout.
// generator: (Random&, ostream&) or (Random&, ostream&, trial) -> void
// checker: (istream& generated_input, istream& candidate_output) -> bool
template <class Generator, class Solution, class Checker,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_streams(RandomTestConfig config, Generator generator,
                              Solution solution, Checker checker,
                              OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    if (config.trials < 0) config.trials = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        std::string input = random_testing_detail::generate_stream_input(
            generator, random, trial);
        std::string output =
            random_testing_detail::run_with_standard_streams(input, solution);
        std::istringstream input_stream(input);
        std::istringstream output_stream(output);
        if (!bool(std::invoke(checker, input_stream, output_stream))) {
            std::invoke(on_failure, std::as_const(input),
                        std::as_const(output), trial, config.seed);
            return random_testing_detail::failure_result(
                config, trial, RandomTestFailure::rejected_output);
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solution, class Checker>
RandomTestResult test_streams(Generator generator, Solution solution,
                              Checker checker) {
    return test_streams(RandomTestConfig(), std::move(generator),
                        std::move(solution), std::move(checker));
}

// generator: (Random&) or (Random&, trial) -> InteractiveTestCase<Input, State>
// solver: (const Input&, interaction) or (interaction) -> Answer
// query_handler: (State&, Query) -> Reply
// validator: (const Input&, const State&, const Answer&) -> bool
template <class Generator, class Solver, class QueryHandler, class Validator,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_interactively(RandomTestConfig config, int query_limit,
                                    Generator generator, Solver solver,
                                    QueryHandler query_handler,
                                    Validator validator,
                                    OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    assert(0 <= query_limit);
    if (config.trials < 0) config.trials = 0;
    if (query_limit < 0) query_limit = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        auto test_case =
            random_testing_detail::invoke_with_trial(generator, random, trial);
        using State = std::remove_cvref_t<decltype(test_case.state)>;
        RandomInteraction<State, QueryHandler> interaction(
            test_case.state, query_handler, query_limit);

        try {
            auto answer = random_testing_detail::invoke_interactive_solver(
                solver, std::as_const(test_case.input), interaction);
            interaction.record_answer(answer);
            if (!bool(std::invoke(validator, std::as_const(test_case.input),
                                  std::as_const(test_case.state),
                                  std::as_const(answer)))) {
                RandomTestResult result =
                    random_testing_detail::failure_result(
                        config, trial, RandomTestFailure::rejected_output,
                        interaction.query_count());
                std::invoke(on_failure, std::as_const(test_case),
                            interaction.transcript(), trial, config.seed,
                            result.failure);
                return result;
            }
        } catch (const random_testing_detail::InteractionAbort& failure) {
            interaction.record_failure(failure.message);
            RandomTestResult result = random_testing_detail::failure_result(
                config, trial, failure.failure, interaction.query_count());
            std::invoke(on_failure, std::as_const(test_case),
                        interaction.transcript(), trial, config.seed,
                        result.failure);
            return result;
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solver, class QueryHandler, class Validator>
RandomTestResult test_interactively(int query_limit, Generator generator,
                                    Solver solver, QueryHandler query_handler,
                                    Validator validator) {
    return test_interactively(RandomTestConfig(), query_limit,
                              std::move(generator), std::move(solver),
                              std::move(query_handler), std::move(validator));
}

// Runs an ordinary interactive solution using std::cin and std::cout.
// generator: (Random&, ostream&) or (Random&, ostream&, trial) -> JudgeState
// query_handler: (JudgeState&, istream& query, ostream& response) -> void
// checker: (istream& public_input, const JudgeState&,
//           istream& final_output) -> bool
template <class Generator, class Solution, class QueryHandler, class Checker,
          class OnFailure = IgnoreRandomTestFailure>
RandomTestResult test_interactive_streams(
    RandomTestConfig config, int query_limit, Generator generator,
    Solution solution, QueryHandler query_handler, Checker checker,
    OnFailure on_failure = {}) {
    assert(0 <= config.trials);
    assert(0 <= query_limit);
    if (config.trials < 0) config.trials = 0;
    if (query_limit < 0) query_limit = 0;
    Random random(config.seed);

    for (int trial = 0; trial < config.trials; trial++) {
        std::ostringstream generated_input;
        auto state =
            random_testing_detail::generate_interactive_stream_input(
                generator, random, generated_input, trial);
        std::string input = generated_input.str();
        std::stringbuf candidate_output(std::ios::out);
        using State = std::remove_cvref_t<decltype(state)>;
        random_testing_detail::InteractiveStreamBuffer<State, QueryHandler>
            input_buffer(state, query_handler, candidate_output, input,
                         query_limit);
        {
            random_testing_detail::StandardStreamRedirect redirect(
                &input_buffer, &candidate_output);
            std::invoke(solution);
        }
        input_buffer.finish();
        if (input_buffer.exception()) {
            std::rethrow_exception(input_buffer.exception());
        }

        RandomTestFailure failure = input_buffer.failure();
        if (failure != RandomTestFailure::none) {
            RandomTestResult result = random_testing_detail::failure_result(
                config, trial, failure, input_buffer.query_count());
            std::invoke(on_failure, std::as_const(input),
                        std::as_const(state), input_buffer.transcript(), trial,
                        config.seed, failure);
            return result;
        }

        std::istringstream input_stream(input);
        std::istringstream output_stream(input_buffer.transcript().answer);
        if (!bool(std::invoke(checker, input_stream, std::as_const(state),
                              output_stream))) {
            RandomTestResult result = random_testing_detail::failure_result(
                config, trial, RandomTestFailure::rejected_output,
                input_buffer.query_count());
            std::invoke(on_failure, std::as_const(input),
                        std::as_const(state), input_buffer.transcript(), trial,
                        config.seed, result.failure);
            return result;
        }
    }
    return random_testing_detail::success_result(config);
}

template <class Generator, class Solution, class QueryHandler, class Checker>
RandomTestResult test_interactive_streams(
    int query_limit, Generator generator, Solution solution,
    QueryHandler query_handler, Checker checker) {
    return test_interactive_streams(
        RandomTestConfig(), query_limit, std::move(generator),
        std::move(solution), std::move(query_handler), std::move(checker));
}

// Short contest interface. Prints failure metadata and terminates on failure.
template <class Property>
RandomTestResult stress_test(Property property, int trials = 1000,
                             std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = random_test(config, std::move(property));
    if (!result) {
        std::cerr << "random test failed: seed=" << result.seed
                  << " trial=" << result.failed_trial << '\n';
        std::abort();
    }
    return result;
}

// Short optimized-versus-brute-force interface.
template <class Generator, class Solver, class Oracle>
requires(!std::integral<std::remove_cvref_t<Solver>> &&
         !std::integral<std::remove_cvref_t<Oracle>>)
RandomTestResult stress_test(Generator generator, Solver solver, Oracle oracle,
                             int trials = 1000,
                             std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = compare_randomly(
        config, std::move(generator), std::move(solver), std::move(oracle),
        PrintRandomTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solver, class Validator>
RandomTestResult constructive_stress_test(
    Generator generator, Solver solver, Validator validator,
    int trials = 1000, std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_constructively(
        config, std::move(generator), std::move(solver),
        std::move(validator), PrintConstructiveTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solution, class Checker>
RandomTestResult stream_stress_test(
    Generator generator, Solution solution, Checker checker,
    int trials = 1000, std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_streams(
        config, std::move(generator), std::move(solution),
        std::move(checker), PrintStreamTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solver, class QueryHandler, class Validator>
RandomTestResult interactive_stress_test(
    int query_limit, Generator generator, Solver solver,
    QueryHandler query_handler, Validator validator, int trials = 1000,
    std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_interactively(
        config, query_limit, std::move(generator), std::move(solver),
        std::move(query_handler), std::move(validator),
        PrintInteractiveTestFailure());
    if (!result) std::abort();
    return result;
}

template <class Generator, class Solution, class QueryHandler, class Checker>
RandomTestResult interactive_stream_stress_test(
    int query_limit, Generator generator, Solution solution,
    QueryHandler query_handler, Checker checker, int trials = 1000,
    std::uint64_t seed = default_random_test_seed) {
    RandomTestConfig config;
    config.trials = trials;
    config.seed = seed;
    RandomTestResult result = test_interactive_streams(
        config, query_limit, std::move(generator), std::move(solution),
        std::move(query_handler), std::move(checker),
        PrintInteractiveStreamTestFailure());
    if (!result) std::abort();
    return result;
}

}  // namespace utilities
}  // namespace m1une

Back to top page