#1182222 (C++23(gcc16)) No.3677 Global Checksum

• 問題: No.3677 Global Checksum
• ユーザー: harurun
• 提出日時: 2026-09-03 16:21:15
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: WA
• 実行時間: -
• コード長: 5,200 bytes
• コンパイル時間: 3,142 ms
• コンパイル使用メモリ: 374,984 KB
• 実行使用メモリ: 43,008 KB
• 最終ジャッジ日時: 2026-09-04 23:12:37
• 合計ジャッジ時間: 7,474 ms
• ジャッジサーバーID （参考情報）: judge4_1 / judge6_0

ファイルパターン	結果
sample	WA * 3
other	WA * 20

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("bmi,bmi2,popcnt")

#include <bits/stdc++.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

using namespace std;

[[noreturn]] static inline void fail() {
    _exit(1);
}

static inline __attribute__((always_inline))
bool digit(unsigned char c) {
    return (unsigned)(c - '0') <= 9;
}

__attribute__((optimize("O3,unroll-loops")))
static void validate(const char* p, const char* e) {
    // H
    if (__builtin_expect(p == e || !digit(*p), 0))
        fail();

    unsigned H = 0;

    do {
        H = H * 10 + (*p++ - '0');

        if (__builtin_expect(H > 1'000'000, 0))
            fail();
    } while (p != e && digit(*p));

    if (__builtin_expect(H < 1, 0))
        fail();

    // exactly one space
    if (__builtin_expect(p == e || *p++ != ' ', 0))
        fail();

    // W
    if (__builtin_expect(p == e || !digit(*p), 0))
        fail();

    unsigned W = 0;

    do {
        W = W * 10 + (*p++ - '0');

        if (__builtin_expect(W > 4'000'000, 0))
            fail();
    } while (p != e && digit(*p));

    if (__builtin_expect(
        W < 1 || (uint64_t)H * W > 4'000'000,
        0
    ))
        fail();

    // EOL after H W
    if (__builtin_expect(p == e, 0))
        fail();

    if (*p == '\n') {
        ++p;
    } else if (
        *p == '\r' &&
        p + 1 < e &&
        p[1] == '\n'
    ) {
        p += 2;
    } else {
        fail();
    }

    /*
        A validation.

        0 <= A <= 1,000,000,000

        数値変換しない。
        significant digits が
          <= 9  -> OK
          ==10  -> 1000000000 のみ OK
          >=11  -> NG

        leading zero は許容。
    */

    const unsigned total = H * W;

    for (unsigned k = 0; k < total; ++k) {
        if (__builtin_expect(p == e || !digit(*p), 0))
            fail();

        /*
            leading zeros を読み飛ばす。

            これにより
              0000000000001
            のような入力も高速に処理できる。
        */
        while (p != e && *p == '0')
            ++p;

        if (p != e && digit(*p)) {
            const char* s = p;

            /*
                最大11桁だけ確認すればよい。

                11 significant digits に達した時点で
                必ず範囲外。
            */
            while (
                p != e &&
                digit(*p) &&
                p - s < 11
            ) {
                ++p;
            }

            size_t n = p - s;

            if (__builtin_expect(n >= 11, 0))
                fail();

            /*
                10 significant digits の場合、
                valid なのは 1000000000 のみ。
            */
            if (__builtin_expect(n == 10, 0)) {
                if (
                    s[0] != '1' ||
                    s[1] != '0' ||
                    s[2] != '0' ||
                    s[3] != '0' ||
                    s[4] != '0' ||
                    s[5] != '0' ||
                    s[6] != '0' ||
                    s[7] != '0' ||
                    s[8] != '0' ||
                    s[9] != '0'
                ) {
                    fail();
                }
            }
        }

        /*
            token の後ろ。
        */
        if (__builtin_expect(p == e, 0))
            fail();

        /*
            行末か space かは k % W を使わない。
            column counter の方が高速。
        */
        unsigned col = (k + 1) % W;

        if (col != 0) {
            if (__builtin_expect(*p++ != ' ', 0))
                fail();
        } else {
            if (*p == '\n') {
                ++p;
            } else if (
                *p == '\r' &&
                p + 1 < e &&
                p[1] == '\n'
            ) {
                p += 2;
            } else {
                fail();
            }
        }
    }

    if (__builtin_expect(p != e, 0))
        fail();
}

int main() {
    struct stat st;

    if (
        fstat(STDIN_FILENO, &st) == 0 &&
        S_ISREG(st.st_mode) &&
        st.st_size > 0
    ) {
        size_t n = (size_t)st.st_size;

        void* m = mmap(
            nullptr,
            n,
            PROT_READ,
            MAP_PRIVATE,
            STDIN_FILENO,
            0
        );

        if (m != MAP_FAILED) {
            madvise(m, n, MADV_SEQUENTIAL);

            validate(
                static_cast<const char*>(m),
                static_cast<const char*>(m) + n
            );

            return 0;
        }
    }

    /*
        pipe fallback
    */
    constexpr size_t MAX_SIZE = 64ULL << 20;

    static char buf[MAX_SIZE];

    size_t n = 0;

    while (n < MAX_SIZE) {
        ssize_t r = read(
            STDIN_FILENO,
            buf + n,
            MAX_SIZE - n
        );

        if (r < 0)
            return 1;

        if (r == 0)
            break;

        n += r;
    }

    if (n == 0)
        return 1;

    /*
        64 MiB を超えていないことも確認。
    */
    if (n == MAX_SIZE) {
        char c;

        if (read(STDIN_FILENO, &c, 1) != 0)
            fail();
    }

    validate(buf, buf + n);
}