結果

問題 No.3677 Global Checksum
コンテスト
ユーザー 👑 みうね
提出日時 2026-09-05 12:10:15
言語 C(gnu17)
(gcc 15.3.0)
コンパイル:
gcc-15 -O2 -std=gnu17 -Wno-error=implicit-function-declaration -Wno-error=implicit-int -Wno-error=incompatible-pointer-types -Wno-error=int-conversion -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 61 ms / 200 ms
+ 210µs
コード長 3,125 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,175 ms
コンパイル使用メモリ 42,880 KB
実行使用メモリ 55,296 KB
最終ジャッジ日時 2026-09-05 14:31:05
合計ジャッジ時間 12,795 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("Ofast,unroll-loops")

#include <stdint.h>
#include <stddef.h>
#include <unistd.h>

#define IN_CAP  (1u << 26)  // 64 MiB
#define OUT_CAP (1u << 24)  // 16 MiB

static unsigned char inbuf[IN_CAP];
static char outbuf[OUT_CAP];

static uint32_t sums[1000000];

/* 0000 ～ 9999 を4文字にしたもの */
static uint32_t dig4[10000];

/* 先頭から何文字捨てればよいか */
static unsigned char lead4[10000];

static inline uint32_t read_u32(unsigned char **pp)
{
    unsigned char *p = *pp;
    uint32_t x = 0;
    unsigned c;

    /*
      呼び出し開始時点では必ず数字。
      数字の直後の空白/改行を1文字消費して終了する。
    */
    while ((c = (unsigned)(*p++ - (unsigned char)'0')) <= 9u) {
        x = x * 10u + c;
    }

    *pp = p;
    return x;
}

int main(void)
{
    /*
      入力全体を最初に読む。
      最大でもだいたい 40MB 程度なので 64MiB に収まる。
    */
    size_t nread = 0;

    while (nread + 1 < IN_CAP) {
        ssize_t z = read(
            STDIN_FILENO,
            inbuf + nread,
            IN_CAP - 1 - nread
        );

        if (z <= 0) break;
        nread += (size_t)z;
    }

    inbuf[nread] = '\n';

    unsigned char *p = inbuf;

    uint32_t H = read_u32(&p);
    uint32_t W = read_u32(&p);

    uint32_t T = 0;

    for (uint32_t i = 0; i < H; ++i) {
        uint32_t s = 0;

        for (uint32_t j = 0; j < W; ++j) {
            s += read_u32(&p);
        }

        sums[i] = s;
        T += s;
    }

    /*
      4桁出力テーブルを作る。
      例えば dig4[123] はメモリ上で "0123"。
    */
    for (uint32_t i = 0; i < 10000; ++i) {
        uint32_t x = i;

        uint32_t a = x / 1000u;
        x -= a * 1000u;

        uint32_t b = x / 100u;
        x -= b * 100u;

        uint32_t c = x / 10u;
        uint32_t d = x - c * 10u;

        dig4[i] =
            (uint32_t)('0' + a) |
            ((uint32_t)('0' + b) << 8) |
            ((uint32_t)('0' + c) << 16) |
            ((uint32_t)('0' + d) << 24);

        lead4[i] =
            i >= 1000u ? 0 :
            i >= 100u  ? 1 :
            i >= 10u   ? 2 :
                         3;
    }

    /*
      後ろから出力を作る。

      10進変換を1桁ずつ /10 せず、
      4桁ずつ /10000 する。
    */
    char *wp = outbuf + OUT_CAP;

    for (uint32_t i = H; i-- != 0;) {
        *--wp = '\n';

        uint32_t v = sums[i] + T;
        uint32_t top;

        do {
            uint32_t q = v / 10000u;
            top = v - q * 10000u;

            wp -= 4;
            __builtin_memcpy(wp, &dig4[top], 4);

            v = q;
        } while (v != 0);

        /* 最上位4桁の不要な 0 を飛ばす */
        wp += lead4[top];
    }

    /*
      全出力をほぼ1回の write で流す。
      最大 10桁 + '\n' × 10^6 < 16MiB。
    */
    size_t left = (size_t)(outbuf + OUT_CAP - wp);

    while (left != 0) {
        ssize_t z = write(STDOUT_FILENO, wp, left);

        if (z <= 0) break;

        wp += z;
        left -= (size_t)z;
    }

    _exit(0);
}
0