include "testlib.h"

include

namespace casegen {

constexpr int kSchemaVersion = 1; constexpr int kTestCount = 100; constexpr int kLimit = 100000;

struct Manifest { int schema; int id; int profile; long long seed;

Manifest() : schema(kSchemaVersion), id(0), profile(0), seed(0) {}
Manifest(int schema_, int id_, int profile_, long long seed_)
    : schema(schema_), id(id_), profile(profile_), seed(seed_) {}

};

struct Operation { int type; int x; int y; };

struct TestCase { std::vector values; std::vector operations; };

struct GeneratedData { std::vector cases; int total_n = 0; int total_q = 0; std::uint64_t answer_count = 0; };

inline int profile_for_id(int id) { if (id <= 8) return 1; if (id <= 20) return 2; if (id <= 35) return 3; if (id <= 50) return 4; if (id <= 85) return 5; return 6; }

inline Manifest manifest_for_id(int id) { if (id < 1 || id > kTestCount) throw std::runtime_error("test id out of range"); // The seed is data, not entropy. Keep it stable across platforms and rebuilds. const std::uint64_t mixed = 0x74320260825ULL ^ (0x9e3779b97f4a7c15ULL * static_cast(id)); return Manifest{kSchemaVersion, id, profile_for_id(id), static_cast(mixed)}; }

inline void seed_testlib(const Manifest& m) { random_t::version = 1; std::vector args = { "casegen-v1", std::to_string(m.id), std::to_string(m.profile), std::to_string(m.seed) }; std::vector argv; argv.reserve(args.size()); for (std::string& arg : args) argv.push_back(&arg[0]); rnd.setSeed(static_cast(argv.size()), argv.data()); }

inline std::vector partition_total(int total, int parts) { if (parts <= 0 || total < parts) throw std::runtime_error("invalid partition"); std::vector result(parts, 1); for (int left = total - parts; left > 0; --left) { ++result[rnd.next(parts)]; } return result; }

inline std::vector make_values(int n, int mode) { std::vector a(n); switch (mode % 8) { case 0: { const int value = rnd.next(0, 1000000000); std::fill(a.begin(), a.end(), value); break; } case 1: for (int i = 0; i < n; ++i) a[i] = i; break; case 2: for (int i = 0; i < n; ++i) a[i] = n - i; break; case 3: for (int i = 0; i < n; ++i) a[i] = (i & 1) ? 0 : 1000000000; break; case 4: for (int& value : a) value = rnd.next(0, 3); break; case 5: { const int width = std::max(2, std::min(n, 97)); for (int i = 0; i < n; ++i) a[i] = (i % width) * (1000000000 / width); break; } case 6: { const std::vector p = rnd.perm(n, 0); for (int i = 0; i < n; ++i) a[i] = p[i]; break; } default: for (int& value : a) value = rnd.next(0, 1000000000); break; } return a; }

inline std::pair make_query_range(int n, int style, int serial) { if (n == 1) return {1, 1}; int l = 1; int r = n; switch (style % 7) { case 0: l = 1; r = n; break; case 1: l = rnd.next(1, n); r = l; break; case 2: { l = rnd.next(1, n); const int length = rnd.next(1, std::min(n - l + 1, 32)); r = l + length - 1; break; } case 3: { l = rnd.next(1, n); const int min_r = std::min(n, l + std::max(0, n / 2 - 1)); r = rnd.next(min_r, n); break; } case 4: l = (serial & 1) ? 1 : std::max(1, n / 3); r = (serial & 1) ? std::max(1, 2 n / 3) : n; break; case 5: { const int boundary = std::min(n, 316 (1 + rnd.next(std::max(1, n / 316)))); l = std::max(1, boundary - rnd.next(0, std::min(319, boundary - 1))); r = std::min(n, boundary + rnd.next(0, std::min(319, n - boundary))); break; } default: l = rnd.next(1, n); r = rnd.next(1, n); if (l > r) std::swap(l, r); break; } return {l, r}; }

inline std::pair make_swap_positions(int n, int style, int serial) { if (n == 1) return {1, 1}; int x = 1; int y = n; switch (style % 7) { case 0: x = rnd.next(1, n); y = x; break; case 1: x = 1; y = n; break; case 2: x = rnd.next(1, n); y = std::min(n, x + 1); break; case 3: x = 1 + (serial % std::min(n, 17)); y = rnd.next(1, n); break; case 4: { const int block_start = 1 + 316 * rnd.next(std::max(1, (n + 315) / 316)); x = std::min(n, block_start + rnd.next(0, std::min(315, n - block_start))); y = std::min(n, block_start + rnd.next(0, std::min(315, n - block_start))); break; } case 5: x = rnd.next(1, n); y = n + 1 - x; break; default: x = rnd.next(1, n); y = rnd.next(1, n); break; } return {x, y}; }

inline std::vector make_operations(int n, int q, int query_percent, int query_style, int swap_style) { std::vector operations; operations.reserve(q); for (int i = 0; i < q; ++i) { bool is_query = rnd.next(100) < query_percent; if (i == q - 1 && std::none_of(operations.begin(), operations.end(), [](const Operation& op) { return op.type == 2; })) { is_query = true; } if (is_query) { const std::pair range = make_query_range(n, query_style + i % 7, i); operations.push_back({2, range.first, range.second}); } else { const std::pair positions = make_swap_positions(n, swap_style + i % 7, i); operations.push_back({1, positions.first, positions.second}); } } return operations; }

inline TestCase make_case(int n, int q, int value_mode, int query_percent, int query_style, int swap_style) { TestCase tc; tc.values = make_values(n, value_mode); tc.operations = make_operations(n, q, query_percent, query_style, swap_style); return tc; }

inline void add_case(GeneratedData& data, TestCase tc) { data.total_n += static_cast(tc.values.size()); data.total_q += static_cast(tc.operations.size()); for (const Operation& op : tc.operations) data.answer_count += (op.type == 2); data.cases.push_back(std::move(tc)); }

inline GeneratedData generate_edge_case(int id) { GeneratedData data; if (id == 1) { add_case(data, TestCase{{0}, {{2, 1, 1}}}); } else if (id == 2) { add_case(data, TestCase{{1000000000}, {{1, 1, 1}, {2, 1, 1}}}); } else if (id == 3) { add_case(data, make_case(100, 500, 0, 80, 0, 0)); } else if (id == 4) { add_case(data, make_case(100000, 12, 2, 100, 0, 1)); } else if (id == 5) { add_case(data, make_case(1000, 5000, 4, 70, 6, 6)); } else if (id == 6) { add_case(data, make_case(4097, 10000, 3, 60, 5, 4)); } else if (id == 7) { add_case(data, make_case(10000, 10000, 1, 95, 1, 0)); } else { for (int n = 1; n <= 64; ++n) add_case(data, make_case(n, n + 3, n, 65, n, n + 2)); } return data; }

inline GeneratedData generate_partitioned(int id, int test_count, int total_n, int total_q) { GeneratedData data; const std::vector ns = partition_total(total_n, test_count); const std::vector qs = partition_total(total_q, test_count); data.cases.reserve(test_count); for (int i = 0; i < test_count; ++i) { const int query_percent = 20 + ((id 19 + i 23) % 76); add_case(data, make_case(ns[i], qs[i], id + i, query_percent, id + 2 i, id + 3 i)); } return data; }

inline GeneratedData generate(const Manifest& manifest) { if (manifest.schema != kSchemaVersion || manifest.id < 1 || manifest.id > kTestCount || manifest.profile != profile_for_id(manifest.id)) { throw std::runtime_error("invalid manifest"); } seed_testlib(manifest); const int id = manifest.id; GeneratedData data; if (id <= 8) { data = generate_edge_case(id); } else if (id <= 20) { static const int counts[] = {100000, 50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50000, 100000}; const int t = counts[id - 9]; data = generate_partitioned(id, t, 100000, 100000); } else if (id <= 35) { const int t = 200 + (id - 21) 113; const int total = 30000 + (id - 21) 3500; data = generate_partitioned(id, t, std::min(kLimit, total), std::min(kLimit, total)); } else if (id <= 50) { const int query_rates[] = {100, 95, 75, 50, 25, 5}; add_case(data, make_case(100000, 100000, id, query_rates[(id - 36) % 6], id, id / 2)); } else if (id <= 85) { const int query_rates[] = {95, 80, 65, 50, 35, 20, 5}; add_case(data, make_case(100000, 100000, 6 + id % 2, query_rates[(id - 51) % 7], id 3, id 5)); } else { static const int counts[] = {2, 3, 5, 10, 20, 50, 100, 250, 500, 1000, 2000, 5000, 10000, 20000, 50000}; data = generate_partitioned(id, counts[id - 86], 100000, 100000); } if (data.cases.empty() || data.total_n > kLimit || data.total_q > kLimit || data.total_n < static_cast(data.cases.size()) || data.total_q < static_cast(data.cases.size())) { throw std::runtime_error("generated data violates global limits"); } return data; }

inline void append_int(std::string& output, long long value) { char buffer[32]; char end = buffer + sizeof(buffer); char cursor = end; do { *--cursor = static_cast('0' + value % 10); value /= 10; } while (value != 0); output.append(cursor, end); }

inline std::string serialize(const GeneratedData& data) { std::string output; output.reserve(static_cast(data.total_n + data.total_q) * 16 + 32); append_int(output, static_cast(data.cases.size())); output.push_back('\n'); for (const TestCase& tc : data.cases) { append_int(output, static_cast(tc.values.size())); output.push_back(' '); append_int(output, static_cast(tc.operations.size())); output.push_back('\n'); for (std::size_t i = 0; i < tc.values.size(); ++i) { if (i) output.push_back(' '); append_int(output, tc.values[i]); } output.push_back('\n'); for (const Operation& op : tc.operations) { append_int(output, op.type); output.push_back(' '); append_int(output, op.x); output.push_back(' '); append_int(output, op.y); output.push_back('\n'); } } return output; }

} // namespace casegen

include

namespace digest {

class Sha256 { public: Sha256() { reset(); }

void reset() {
    state_ = {0x6a09e667U, 0xbb67ae85U, 0x3c6ef372U, 0xa54ff53aU,
              0x510e527fU, 0x9b05688cU, 0x1f83d9abU, 0x5be0cd19U};
    bit_count_ = 0;
    buffer_size_ = 0;
}

void update(const void* raw, std::size_t size) {
    const auto* data = static_cast<const std::uint8_t*>(raw);
    bit_count_ += static_cast<std::uint64_t>(size) * 8;
    while (size > 0) {
        const std::size_t take = std::min(size, buffer_.size() - buffer_size_);
        for (std::size_t i = 0; i < take; ++i) buffer_[buffer_size_ + i] = data[i];
        buffer_size_ += take;
        data += take;
        size -= take;
        if (buffer_size_ == buffer_.size()) {
            transform(buffer_.data());
            buffer_size_ = 0;
        }
    }
}

void update_u64(std::uint64_t value) {
    std::uint8_t bytes[8];
    for (int i = 0; i < 8; ++i) bytes[i] = static_cast<std::uint8_t>(value >> (8 * i));
    update(bytes, sizeof(bytes));
}

std::string final_hex() {
    const std::uint64_t original_bits = bit_count_;
    const std::uint8_t marker = 0x80;
    update(&marker, 1);
    const std::uint8_t zero = 0;
    while (buffer_size_ != 56) update(&zero, 1);
    std::uint8_t length[8];
    for (int i = 0; i < 8; ++i) length[7 - i] = static_cast<std::uint8_t>(original_bits >> (8 * i));
    update(length, sizeof(length));
    static constexpr char hex[] = "0123456789abcdef";
    std::string result;
    result.reserve(64);
    for (std::uint32_t word : state_) {
        for (int shift = 28; shift >= 0; shift -= 4) result.push_back(hex[(word >> shift) & 15]);
    }
    return result;
}

private: static std::uint32_t rotr(std::uint32_t x, int n) { return (x >> n) | (x << (32 - n)); }

void transform(const std::uint8_t* block) {
    static constexpr std::uint32_t k[64] = {
        0x428a2f98U,0x71374491U,0xb5c0fbcfU,0xe9b5dba5U,0x3956c25bU,0x59f111f1U,0x923f82a4U,0xab1c5ed5U,
        0xd807aa98U,0x12835b01U,0x243185beU,0x550c7dc3U,0x72be5d74U,0x80deb1feU,0x9bdc06a7U,0xc19bf174U,
        0xe49b69c1U,0xefbe4786U,0x0fc19dc6U,0x240ca1ccU,0x2de92c6fU,0x4a7484aaU,0x5cb0a9dcU,0x76f988daU,
        0x983e5152U,0xa831c66dU,0xb00327c8U,0xbf597fc7U,0xc6e00bf3U,0xd5a79147U,0x06ca6351U,0x14292967U,
        0x27b70a85U,0x2e1b2138U,0x4d2c6dfcU,0x53380d13U,0x650a7354U,0x766a0abbU,0x81c2c92eU,0x92722c85U,
        0xa2bfe8a1U,0xa81a664bU,0xc24b8b70U,0xc76c51a3U,0xd192e819U,0xd6990624U,0xf40e3585U,0x106aa070U,
        0x19a4c116U,0x1e376c08U,0x2748774cU,0x34b0bcb5U,0x391c0cb3U,0x4ed8aa4aU,0x5b9cca4fU,0x682e6ff3U,
        0x748f82eeU,0x78a5636fU,0x84c87814U,0x8cc70208U,0x90befffaU,0xa4506cebU,0xbef9a3f7U,0xc67178f2U};
    std::uint32_t w[64];
    for (int i = 0; i < 16; ++i) {
        w[i] = (static_cast<std::uint32_t>(block[4*i]) << 24) |
               (static_cast<std::uint32_t>(block[4*i+1]) << 16) |
               (static_cast<std::uint32_t>(block[4*i+2]) << 8) |
               static_cast<std::uint32_t>(block[4*i+3]);
    }
    for (int i = 16; i < 64; ++i) {
        const std::uint32_t s0 = rotr(w[i-15],7) ^ rotr(w[i-15],18) ^ (w[i-15] >> 3);
        const std::uint32_t s1 = rotr(w[i-2],17) ^ rotr(w[i-2],19) ^ (w[i-2] >> 10);
        w[i] = w[i-16] + s0 + w[i-7] + s1;
    }
    std::uint32_t a=state_[0], b=state_[1], c=state_[2], d=state_[3];
    std::uint32_t e=state_[4], f=state_[5], g=state_[6], h=state_[7];
    for (int i = 0; i < 64; ++i) {
        const std::uint32_t s1 = rotr(e,6) ^ rotr(e,11) ^ rotr(e,25);
        const std::uint32_t ch = (e & f) ^ (~e & g);
        const std::uint32_t temp1 = h + s1 + ch + k[i] + w[i];
        const std::uint32_t s0 = rotr(a,2) ^ rotr(a,13) ^ rotr(a,22);
        const std::uint32_t maj = (a & b) ^ (a & c) ^ (b & c);
        const std::uint32_t temp2 = s0 + maj;
        h=g; g=f; f=e; e=d+temp1; d=c; c=b; b=a; a=temp1+temp2;
    }
    state_[0]+=a; state_[1]+=b; state_[2]+=c; state_[3]+=d;
    state_[4]+=e; state_[5]+=f; state_[6]+=g; state_[7]+=h;
}

std::array<std::uint32_t, 8> state_{};
std::array<std::uint8_t, 64> buffer_{};
std::uint64_t bit_count_ = 0;
std::size_t buffer_size_ = 0;

};

inline std::string sha256(const std::string& value) { Sha256 hash; hash.update(value.data(), value.size()); return hash.final_hex(); }

} // namespace digest

include

namespace {

struct Metadata { casegen::Manifest manifest; std::string input_hash; long long answer_count; std::string answer_hash; };

bool is_lower_hex(const std::string& value) { if (value.size() != 64) return false; for (char c : value) if (!((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f'))) return false; return true; }

Metadata read_metadata(const char input_path, const char answer_path) { Metadata metadata; std::ifstream input(input_path); std::ifstream answer(answer_path); std::string magic; if (!(input >> magic >> metadata.manifest.schema >> metadata.manifest.id >> metadata.manifest.profile >> metadata.manifest.seed) || magic != "DG743") { throw std::runtime_error("invalid manifest file"); } input >> std::ws; if (!input.eof()) throw std::runtime_error("extra tokens in manifest file"); int answer_schema = 0; if (!(answer >> magic >> answer_schema >> metadata.input_hash >> metadata.answer_count >> metadata.answer_hash) || magic != "DG743_ANS" || answer_schema != 1 || metadata.answer_count < 0 || metadata.answer_count > casegen::kLimit || !is_lower_hex(metadata.input_hash) || !is_lower_hex(metadata.answer_hash)) { throw std::runtime_error("invalid answer metadata file"); } answer >> std::ws; if (!answer.eof()) throw std::runtime_error("extra tokens in answer metadata file"); return metadata; }

} // namespace

int main(int argc, char* argv) { // Register immediately, as required for a UOJ auxiliary program. This testlib // probes ouf during registration, so registration may wait for the first answer; // the main thread remains available to generate and send the batch input. std::thread registration(& { registerTestlibCmd(argc, argv); }); std::signal(SIGPIPE, SIG_IGN); Metadata metadata; casegen::GeneratedData data; std::string input; try { metadata = read_metadata(argv[1], argv[3]); data = casegen::generate(metadata.manifest); input = casegen::serialize(data); } catch (const std::exception& error) { std::fprintf(stderr, "FAIL generator setup failed: %s\n", error.what()); std::fflush(stderr); std::_Exit(FAIL_EXIT_CODE); } if (data.answer_count != static_cast(metadata.answer_count)) { std::fprintf(stderr, "FAIL answer count metadata mismatch\n"); std::fflush(stderr); std::_Exit(FAIL_EXIT_CODE); } const std::string actual_input_hash = digest::sha256(input); if (actual_input_hash != metadata.input_hash) { std::fprintf(stderr, "FAIL generated input digest mismatch on test %d\n", metadata.manifest.id); std::fflush(stderr); std::_Exit(FAIL_EXIT_CODE); } std::atomic write_failed(false); std::thread writer(& { const char cursor = input.data(); std::size_t remaining = input.size(); while (remaining > 0) { const ssize_t written = ::write(STDOUT_FILENO, cursor, remaining); if (written > 0) { cursor += written; remaining -= static_cast(written); } else if (written < 0 && errno == EINTR) { continue; } else { write_failed.store(true); break; } } });

registration.join();

digest::Sha256 answer_hash;
for (long long index = 0; index < metadata.answer_count; ++index) {
    const long long value = ouf.readLong(0, 4999950000LL,
                                         "answer #" + std::to_string(index + 1));
    answer_hash.update_u64(static_cast<std::uint64_t>(value));
}
writer.join();
if (write_failed.load()) quitf(_wa, "contestant stopped reading generated input");
if (!ouf.seekEof()) quitf(_wa, "extra output after %lld answers", metadata.answer_count);

const std::string actual_answer_hash = answer_hash.final_hex();
if (actual_answer_hash != metadata.answer_hash) {
    quitf(_wa, "wrong answer digest on test %d (%lld answers)",
          metadata.manifest.id, metadata.answer_count);
}
quitf(_ok, "accepted test %d: T=%d, sum(n)=%d, sum(Q)=%d, answers=%lld",
      metadata.manifest.id, static_cast<int>(data.cases.size()), data.total_n, data.total_q,
      metadata.answer_count);

}

ifndef DATA_CASEGEN_H

define DATA_CASEGEN_H

include "testlib.h"

include

namespace casegen {

constexpr int kSchemaVersion = 1; constexpr int kTestCount = 100; constexpr int kLimit = 100000;

struct Manifest { int schema; int id; int profile; long long seed;

Manifest() : schema(kSchemaVersion), id(0), profile(0), seed(0) {}
Manifest(int schema_, int id_, int profile_, long long seed_)
    : schema(schema_), id(id_), profile(profile_), seed(seed_) {}

};

struct Operation { int type; int x; int y; };

struct TestCase { std::vector values; std::vector operations; };

struct GeneratedData { std::vector cases; int total_n = 0; int total_q = 0; std::uint64_t answer_count = 0; };

inline int profile_for_id(int id) { if (id <= 8) return 1; if (id <= 20) return 2; if (id <= 35) return 3; if (id <= 50) return 4; if (id <= 85) return 5; return 6; }

} // namespace casegen

endif

ifndef DATA_SHA256_H

define DATA_SHA256_H

include

namespace digest {

class Sha256 { public: Sha256() { reset(); }

void reset() {
    state_ = {0x6a09e667U, 0xbb67ae85U, 0x3c6ef372U, 0xa54ff53aU,
              0x510e527fU, 0x9b05688cU, 0x1f83d9abU, 0x5be0cd19U};
    bit_count_ = 0;
    buffer_size_ = 0;
}

void update(const void* raw, std::size_t size) {
    const auto* data = static_cast<const std::uint8_t*>(raw);
    bit_count_ += static_cast<std::uint64_t>(size) * 8;
    while (size > 0) {
        const std::size_t take = std::min(size, buffer_.size() - buffer_size_);
        for (std::size_t i = 0; i < take; ++i) buffer_[buffer_size_ + i] = data[i];
        buffer_size_ += take;
        data += take;
        size -= take;
        if (buffer_size_ == buffer_.size()) {
            transform(buffer_.data());
            buffer_size_ = 0;
        }
    }
}

void update_u64(std::uint64_t value) {
    std::uint8_t bytes[8];
    for (int i = 0; i < 8; ++i) bytes[i] = static_cast<std::uint8_t>(value >> (8 * i));
    update(bytes, sizeof(bytes));
}

std::string final_hex() {
    const std::uint64_t original_bits = bit_count_;
    const std::uint8_t marker = 0x80;
    update(&marker, 1);
    const std::uint8_t zero = 0;
    while (buffer_size_ != 56) update(&zero, 1);
    std::uint8_t length[8];
    for (int i = 0; i < 8; ++i) length[7 - i] = static_cast<std::uint8_t>(original_bits >> (8 * i));
    update(length, sizeof(length));
    static constexpr char hex[] = "0123456789abcdef";
    std::string result;
    result.reserve(64);
    for (std::uint32_t word : state_) {
        for (int shift = 28; shift >= 0; shift -= 4) result.push_back(hex[(word >> shift) & 15]);
    }
    return result;
}

private: static std::uint32_t rotr(std::uint32_t x, int n) { return (x >> n) | (x << (32 - n)); }

void transform(const std::uint8_t* block) {
    static constexpr std::uint32_t k[64] = {
        0x428a2f98U,0x71374491U,0xb5c0fbcfU,0xe9b5dba5U,0x3956c25bU,0x59f111f1U,0x923f82a4U,0xab1c5ed5U,
        0xd807aa98U,0x12835b01U,0x243185beU,0x550c7dc3U,0x72be5d74U,0x80deb1feU,0x9bdc06a7U,0xc19bf174U,
        0xe49b69c1U,0xefbe4786U,0x0fc19dc6U,0x240ca1ccU,0x2de92c6fU,0x4a7484aaU,0x5cb0a9dcU,0x76f988daU,
        0x983e5152U,0xa831c66dU,0xb00327c8U,0xbf597fc7U,0xc6e00bf3U,0xd5a79147U,0x06ca6351U,0x14292967U,
        0x27b70a85U,0x2e1b2138U,0x4d2c6dfcU,0x53380d13U,0x650a7354U,0x766a0abbU,0x81c2c92eU,0x92722c85U,
        0xa2bfe8a1U,0xa81a664bU,0xc24b8b70U,0xc76c51a3U,0xd192e819U,0xd6990624U,0xf40e3585U,0x106aa070U,
        0x19a4c116U,0x1e376c08U,0x2748774cU,0x34b0bcb5U,0x391c0cb3U,0x4ed8aa4aU,0x5b9cca4fU,0x682e6ff3U,
        0x748f82eeU,0x78a5636fU,0x84c87814U,0x8cc70208U,0x90befffaU,0xa4506cebU,0xbef9a3f7U,0xc67178f2U};
    std::uint32_t w[64];
    for (int i = 0; i < 16; ++i) {
        w[i] = (static_cast<std::uint32_t>(block[4*i]) << 24) |
               (static_cast<std::uint32_t>(block[4*i+1]) << 16) |
               (static_cast<std::uint32_t>(block[4*i+2]) << 8) |
               static_cast<std::uint32_t>(block[4*i+3]);
    }
    for (int i = 16; i < 64; ++i) {
        const std::uint32_t s0 = rotr(w[i-15],7) ^ rotr(w[i-15],18) ^ (w[i-15] >> 3);
        const std::uint32_t s1 = rotr(w[i-2],17) ^ rotr(w[i-2],19) ^ (w[i-2] >> 10);
        w[i] = w[i-16] + s0 + w[i-7] + s1;
    }
    std::uint32_t a=state_[0], b=state_[1], c=state_[2], d=state_[3];
    std::uint32_t e=state_[4], f=state_[5], g=state_[6], h=state_[7];
    for (int i = 0; i < 64; ++i) {
        const std::uint32_t s1 = rotr(e,6) ^ rotr(e,11) ^ rotr(e,25);
        const std::uint32_t ch = (e & f) ^ (~e & g);
        const std::uint32_t temp1 = h + s1 + ch + k[i] + w[i];
        const std::uint32_t s0 = rotr(a,2) ^ rotr(a,13) ^ rotr(a,22);
        const std::uint32_t maj = (a & b) ^ (a & c) ^ (b & c);
        const std::uint32_t temp2 = s0 + maj;
        h=g; g=f; f=e; e=d+temp1; d=c; c=b; b=a; a=temp1+temp2;
    }
    state_[0]+=a; state_[1]+=b; state_[2]+=c; state_[3]+=d;
    state_[4]+=e; state_[5]+=f; state_[6]+=g; state_[7]+=h;
}

std::array<std::uint32_t, 8> state_{};
std::array<std::uint8_t, 64> buffer_{};
std::uint64_t bit_count_ = 0;
std::size_t buffer_size_ = 0;

};

inline std::string sha256(const std::string& value) { Sha256 hash; hash.update(value.data(), value.size()); return hash.final_hex(); }

} // namespace digest

endif

ifndef DATA_REFERENCE_SOLVER_H

define DATA_REFERENCE_SOLVER_H

include "casegen.h"

include "sha256.h"

include

namespace reference_solver {

using OrderedTree = __gnu_pbds::tree< std::pair, __gnu_pbds::null_type, std::less>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

class MatrixFenwick { public: explicit MatrixFenwick(int size) : size_(size), bit_(size + 1, std::vector(size + 1)) {}

void add(int x, int y, long long delta) {
    if (delta == 0) return;
    for (int i = x + 1; i <= size_; i += i & -i) {
        for (int j = y + 1; j <= size_; j += j & -j) bit_[i][j] += delta;
    }
}

long long rectangle(int x1, int y1, int x2, int y2) const {
    if (x1 > x2 || y1 > y2) return 0;
    return prefix(x2, y2) - prefix(x1 - 1, y2) - prefix(x2, y1 - 1) + prefix(x1 - 1, y1 - 1);
}

private: long long prefix(int x, int y) const { long long result = 0; for (int i = x + 1; i > 0; i -= i & -i) { for (int j = y + 1; j > 0; j -= j & -j) result += bit_[i][j]; } return result; }

int size_;
std::vector<std::vector<long long>> bit_;

};

class BlockRangeCounter { public: explicit BlockRangeCounter(int blocks) : blocks_(blocks), tree_(4 * std::max(1, blocks)) {}

void insert(int block, int value, int position) { update(1, 0, blocks_ - 1, block, value, position, true); }
void erase(int block, int value, int position) { update(1, 0, blocks_ - 1, block, value, position, false); }

long long less(int left_block, int right_block, int value) const {
    if (left_block > right_block) return 0;
    return query_less(1, 0, blocks_ - 1, left_block, right_block, value);
}

long long less_equal(int left_block, int right_block, int value) const {
    if (value == 1000000000) return count(left_block, right_block);
    return less(left_block, right_block, value + 1);
}

long long count(int left_block, int right_block) const {
    if (left_block > right_block) return 0;
    return query_count(1, 0, blocks_ - 1, left_block, right_block);
}

private: void update(int node, int left, int right, int target, int value, int position, bool add) { if (add) tree_[node].insert({value, position}); else tree_[node].erase({value, position}); if (left == right) return; const int middle = (left + right) / 2; if (target <= middle) update(node 2, left, middle, target, value, position, add); else update(node 2 + 1, middle + 1, right, target, value, position, add); }

long long query_less(int node, int left, int right, int ql, int qr, int value) const {
    if (ql <= left && right <= qr) return tree_[node].order_of_key({value, -1});
    const int middle = (left + right) / 2;
    long long result = 0;
    if (ql <= middle) result += query_less(node * 2, left, middle, ql, qr, value);
    if (qr > middle) result += query_less(node * 2 + 1, middle + 1, right, ql, qr, value);
    return result;
}

long long query_count(int node, int left, int right, int ql, int qr) const {
    if (ql <= left && right <= qr) return static_cast<long long>(tree_[node].size());
    const int middle = (left + right) / 2;
    long long result = 0;
    if (ql <= middle) result += query_count(node * 2, left, middle, ql, qr);
    if (qr > middle) result += query_count(node * 2 + 1, middle + 1, right, ql, qr);
    return result;
}

int blocks_;
std::vector<OrderedTree> tree_;

};

inline long long inversion_count(std::vector values) { if (values.size() < 2) return 0; std::vector buffer(values.size()); std::function solve = [&](int left, int right) -> long long { if (right - left <= 1) return 0; const int middle = (left + right) / 2; long long answer = solve(left, middle) + solve(middle, right); int i = left; int j = middle; int out = left; while (i < middle && j < right) { if (values[i] <= values[j]) buffer[out++] = values[i++]; else { answer += middle - i; buffer[out++] = values[j++]; } } while (i < middle) buffer[out++] = values[i++]; while (j < right) buffer[out++] = values[j++]; std::copy(buffer.begin() + left, buffer.begin() + right, values.begin() + left); return answer; }; return solve(0, static_cast(values.size())); }

inline long long cross_count(std::vector left, std::vector right) { std::sort(left.begin(), left.end()); std::sort(right.begin(), right.end()); long long answer = 0; std::size_t j = 0; for (int value : left) { while (j < right.size() && right[j] < value) ++j; answer += static_cast(j); } return answer; }

class DynamicInversions { public: explicit DynamicInversions(const std::vector& initial) : n_(static_cast(initial.size())), block_size_(std::max(1, static_cast(std::sqrt(n_)) + 1)), block_count_((n_ + block_size_ - 1) / block_size_), values_(initial), sorted_(block_count_), pair_(block_count_, std::vector(block_count_)), matrix_(block_count_), counter_(block_count_) { for (int i = 0; i < n_; ++i) { sorted_[block_of(i)].push_back(values_[i]); counter_.insert(block_of(i), values_[i], i); } for (auto& block : sorted_) std::sort(block.begin(), block.end()); for (int i = 0; i < block_count_; ++i) { pair_[i][i] = inversion_count(slice(block_start(i), block_end(i))); matrix_.add(i, i, pair_[i][i]); for (int j = i + 1; j < block_count_; ++j) { long long count = 0; for (int value : sorted_[i]) { count += std::lower_bound(sorted_[j].begin(), sorted_[j].end(), value) - sorted_[j].begin(); } pair_[i][j] = count; matrix_.add(i, j, count); } } }

long long query(int left, int right) const {
    --left;
    --right;
    const int left_block = block_of(left);
    const int right_block = block_of(right);
    if (left_block == right_block) return inversion_count(slice(left, right + 1));

    const int left_end = block_end(left_block);
    const int right_start = block_start(right_block);
    std::vector<int> left_fringe = slice(left, left_end);
    std::vector<int> right_fringe = slice(right_start, right + 1);
    long long answer = inversion_count(left_fringe) + inversion_count(right_fringe) +
                       cross_count(left_fringe, right_fringe);
    const int middle_left = left_block + 1;
    const int middle_right = right_block - 1;
    if (middle_left <= middle_right) {
        answer += matrix_.rectangle(middle_left, middle_left, middle_right, middle_right);
        const long long middle_size = counter_.count(middle_left, middle_right);
        for (int value : left_fringe) answer += counter_.less(middle_left, middle_right, value);
        for (int value : right_fringe) {
            answer += middle_size - counter_.less_equal(middle_left, middle_right, value);
        }
    }
    return answer;
}

void swap_positions(int x, int y) {
    --x;
    --y;
    if (x == y || values_[x] == values_[y]) return;
    const int first = values_[x];
    const int second = values_[y];
    modify(x, second);
    modify(y, first);
}

private: int block_of(int position) const { return position / block_size_; } int block_start(int block) const { return block block_size_; } int block_end(int block) const { return std::min(n_, (block + 1) block_size_); }

std::vector<int> slice(int left, int right) const {
    return std::vector<int>(values_.begin() + left, values_.begin() + right);
}

long long less_in_block(int block, int value) const {
    return std::lower_bound(sorted_[block].begin(), sorted_[block].end(), value) - sorted_[block].begin();
}

long long greater_in_block(int block, int value) const {
    return sorted_[block].end() - std::upper_bound(sorted_[block].begin(), sorted_[block].end(), value);
}

void change_pair(int left_block, int right_block, long long delta) {
    if (delta == 0) return;
    pair_[left_block][right_block] += delta;
    matrix_.add(left_block, right_block, delta);
}

void modify(int position, int new_value) {
    const int block = block_of(position);
    const int old_value = values_[position];
    if (old_value == new_value) return;
    for (int other = 0; other < block; ++other) {
        change_pair(other, block, greater_in_block(other, new_value) - greater_in_block(other, old_value));
    }
    for (int other = block + 1; other < block_count_; ++other) {
        change_pair(block, other, less_in_block(other, new_value) - less_in_block(other, old_value));
    }

    counter_.erase(block, old_value, position);
    auto erase_it = std::lower_bound(sorted_[block].begin(), sorted_[block].end(), old_value);
    sorted_[block].erase(erase_it);
    sorted_[block].insert(std::lower_bound(sorted_[block].begin(), sorted_[block].end(), new_value), new_value);
    values_[position] = new_value;
    counter_.insert(block, new_value, position);

    const long long new_inside = inversion_count(slice(block_start(block), block_end(block)));
    change_pair(block, block, new_inside - pair_[block][block]);
}

int n_;
int block_size_;
int block_count_;
std::vector<int> values_;
std::vector<std::vector<int>> sorted_;
std::vector<std::vector<long long>> pair_;
MatrixFenwick matrix_;
BlockRangeCounter counter_;

};

struct AnswerDigest { std::uint64_t count = 0; std::string hex; };

inline AnswerDigest solve(const casegen::GeneratedData& data) { digest::Sha256 hash; std::uint64_t count = 0; for (const casegen::TestCase& tc : data.cases) { DynamicInversions solver(tc.values); for (const casegen::Operation& op : tc.operations) { if (op.type == 1) solver.swap_positions(op.x, op.y); else { hash.update_u64(static_cast(solver.query(op.x, op.y))); ++count; } } } return {count, hash.final_hex()}; }

inline AnswerDigest solve_bruteforce(const casegen::GeneratedData& data) { digest::Sha256 hash; std::uint64_t count = 0; for (const casegen::TestCase& tc : data.cases) { std::vector values = tc.values; for (const casegen::Operation& op : tc.operations) { if (op.type == 1) std::swap(values[op.x - 1], values[op.y - 1]); else { long long answer = 0; for (int i = op.x - 1; i < op.y; ++i) { for (int j = i + 1; j < op.y; ++j) answer += values[i] > values[j]; } hash.update_u64(static_cast(answer)); ++count; } } } return {count, hash.final_hex()}; }

} // namespace reference_solver

wfirstzhang 的博客

博客

743

include "testlib.h"

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

ifndef DATA_CASEGEN_H

define DATA_CASEGEN_H

include "testlib.h"

include

include

include

include

include

include

endif

ifndef DATA_SHA256_H

define DATA_SHA256_H

include

include

include

include

endif

ifndef DATA_REFERENCE_SOLVER_H

define DATA_REFERENCE_SOLVER_H

include "casegen.h"

include "sha256.h"

include

include

include

include

include

include

include

include

endif

评论

发表评论