結果
| 問題 | No.3677 Global Checksum |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-09-03 23:01:44 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,788 bytes |
| 記録 | |
| コンパイル時間 | 622 ms |
| コンパイル使用メモリ | 76,628 KB |
| 実行使用メモリ | 9,784 KB |
| 最終ジャッジ日時 | 2026-09-04 23:13:25 |
| 合計ジャッジ時間 | 5,152 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge5_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 TLE * 1 -- * 6 |
ソースコード
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <array>
using u32 = uint32_t;
using u64 = uint64_t;
alignas(64) static u32 S[1000000];
// "12345678" -> 12345678
static inline __attribute__((always_inline))
u32 parse8(u64 x) {
x = ((x & 0x0F0F0F0F0F0F0F0FULL) * 2561ULL) >> 8;
x = ((x & 0x00FF00FF00FF00FFULL) * 6553601ULL) >> 16;
x &= 0x0000FFFF0000FFFFULL;
// ここまでで
// low = 上4桁
// high = 下4桁
//
// 巨大な 64bit multiply を使わずに合成
return (u32)x * 10000u + (u32)(x >> 32);
}
class FastInput {
static constexpr size_t N = 1u << 15;
alignas(64) char buf[N + 64];
char* p = buf;
char* e = buf;
char* lim = buf;
char* lim4 = buf;
__attribute__((noinline))
void refill() {
const size_t rem = (size_t)(e - p);
if (rem) {
std::memmove(buf, p, rem);
}
p = buf;
e = buf + rem;
const size_t want = N - rem;
const size_t got =
fread_unlocked(e, 1, want, stdin);
e += got;
if (__builtin_expect(got < want, 0)) {
// EOF 付近の先読み用
std::memset(e, 0, 48);
lim = e;
lim4 = e;
}
else {
lim = e - 16;
lim4 = e - 48;
}
}
// バッファ境界チェックなし
inline __attribute__((always_inline))
u32 raw() {
u64 x;
std::memcpy(&x, p, 8);
// ASCII 数字は全て bit 4 が立っている。
// ' ' '\n' 等では立っていない。
constexpr u64 DIG =
0x1010101010101010ULL;
// 先頭8文字が全部数字
if (__builtin_expect((x & DIG) == DIG, 1)) {
u32 v = parse8(x);
// A < 10^9 なので
// 9文字目が数字なら必ず「9桁」
if (p[8] >= '0') {
v = v * 10u
+ (u32)(p[8] - '0');
// 9桁 + separator
p += 10;
}
else {
// 8桁 + separator
p += 9;
}
return v;
}
// 1～7桁。
// ループを使わず完全展開。
u32 v = (u32)(p[0] - '0');
if (p[1] < '0') {
p += 2;
return v;
}
v = v * 10u + (u32)(p[1] - '0');
if (p[2] < '0') {
p += 3;
return v;
}
v = v * 10u + (u32)(p[2] - '0');
if (p[3] < '0') {
p += 4;
return v;
}
v = v * 10u + (u32)(p[3] - '0');
if (p[4] < '0') {
p += 5;
return v;
}
v = v * 10u + (u32)(p[4] - '0');
if (p[5] < '0') {
p += 6;
return v;
}
v = v * 10u + (u32)(p[5] - '0');
if (p[6] < '0') {
p += 7;
return v;
}
v = v * 10u + (u32)(p[6] - '0');
p += 8;
return v;
}
public:
inline __attribute__((always_inline))
u32 next() {
if (__builtin_expect(p >= lim, 0)) {
refill();
}
return raw();
}
inline __attribute__((always_inline))
u32 sum4() {
// 4個分を読むので境界判定も4回ではなく1回
if (__builtin_expect(p >= lim4, 0)) {
refill();
}
constexpr u64 DIG =
0x1010101010101010ULL;
u64 a, b, c, d;
std::memcpy(&a, p, 8);
std::memcpy(&b, p + 10, 8);
std::memcpy(&c, p + 20, 8);
std::memcpy(&d, p + 30, 8);
// 4個とも9桁の場合の高速経路。
//
// A < 10^9 なので、
// 最初の8文字と9文字目が数字なら
// その値は必ずちょうど9桁。
if (__builtin_expect(
((a & b & c & d) & DIG) == DIG &&
(p[8] & p[18] & p[28] & p[38] & 0x10),
1
)) {
u32 s =
parse8(a) * 10u
+ (u32)(p[8] - '0');
s +=
parse8(b) * 10u
+ (u32)(p[18] - '0');
s +=
parse8(c) * 10u
+ (u32)(p[28] - '0');
s +=
parse8(d) * 10u
+ (u32)(p[38] - '0');
p += 40;
return s;
}
// 9桁以外を含んでいても正しく処理
return raw()
+ raw()
+ raw()
+ raw();
}
};
// ------------------------------------------------------------
// 出力
// ------------------------------------------------------------
// 0000 ... 9999 を little-endian の u32 として保持
constexpr std::array<u32, 10000> makeD4() {
std::array<u32, 10000> a{};
for (u32 x = 0; x < 10000; ++x) {
u32 v = x;
const u32 d3 = v % 10;
v /= 10;
const u32 d2 = v % 10;
v /= 10;
const u32 d1 = v % 10;
const u32 d0 = v / 10;
a[x] =
(u32)('0' + d0)
| (u32)('0' + d1) << 8
| (u32)('0' + d2) << 16
| (u32)('0' + d3) << 24;
}
return a;
}
alignas(64)
static constexpr auto D4 = makeD4();
static inline __attribute__((always_inline))
char* put4(char* p, u32 x) {
const u32 v = D4[x];
std::memcpy(p, &v, 4);
return p + 4;
}
// 1～4桁。
// D4 の先頭の '0' を shift で捨てる。
static inline __attribute__((always_inline))
char* put1to4(char* p, u32 x) {
u32 v = D4[x];
if (x >= 1000u) {
std::memcpy(p, &v, 4);
return p + 4;
}
if (x >= 100u) {
v >>= 8;
// 4 byte 書いても、次の書き込みで上書きされる。
std::memcpy(p, &v, 4);
return p + 3;
}
if (x >= 10u) {
v >>= 16;
std::memcpy(p, &v, 4);
return p + 2;
}
v >>= 24;
std::memcpy(p, &v, 4);
return p + 1;
}
static inline __attribute__((always_inline))
char* putU32(char* p, u32 x) {
if (x < 10000u) {
return put1to4(p, x);
}
// base 10000 に分割
const u32 q =
x / 10000u;
const u32 lo =
x - q * 10000u;
if (q < 10000u) {
p = put1to4(p, q);
return put4(p, lo);
}
const u32 hi =
q / 10000u;
const u32 mid =
q - hi * 10000u;
p = put1to4(p, hi);
p = put4(p, mid);
return put4(p, lo);
}
class FastOutput {
static constexpr size_t N =
1u << 15;
alignas(64)
char buf[N + 16];
char* p = buf;
__attribute__((noinline))
void flush() {
fwrite_unlocked(
buf,
1,
(size_t)(p - buf),
stdout
);
p = buf;
}
public:
~FastOutput() {
if (p != buf) {
flush();
}
}
inline __attribute__((always_inline))
void write(u32 x) {
if (__builtin_expect(
p > buf + N - 16,
0
)) {
flush();
}
p = putU32(p, x);
*p++ = '\n';
}
};
// ------------------------------------------------------------
int main() {
FastInput in;
FastOutput out;
const u32 H = in.next();
const u32 W = in.next();
u32 T = 0;
// H が最大になる領域では W <= 4 なので、
// ここを特別扱いしてループ制御を消す。
if (W == 1) {
for (u32 i = 0; i < H; ++i) {
const u32 s = in.next();
S[i] = s;
T += s;
}
}
else if (W == 2) {
for (u32 i = 0; i < H; ++i) {
const u32 s =
in.next()
+ in.next();
S[i] = s;
T += s;
}
}
else if (W == 3) {
for (u32 i = 0; i < H; ++i) {
const u32 s =
in.next()
+ in.next()
+ in.next();
S[i] = s;
T += s;
}
}
else if (W == 4) {
for (u32 i = 0; i < H; ++i) {
const u32 s =
in.sum4();
S[i] = s;
T += s;
}
}
else {
for (u32 i = 0; i < H; ++i) {
u32 s = 0;
u32 j = 0;
for (; j + 4 <= W; j += 4) {
s += in.sum4();
}
for (; j < W; ++j) {
s += in.next();
}
S[i] = s;
T += s;
}
}
for (u32 i = 0; i < H; ++i) {
out.write(S[i] + T);
}
return 0;
}