結果
| 問題 | No.3677 Global Checksum |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-09-03 16:19:16 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,918 bytes |
| 記録 | |
| コンパイル時間 | 1,199 ms |
| コンパイル使用メモリ | 208,952 KB |
| 実行使用メモリ | 42,752 KB |
| 最終ジャッジ日時 | 2026-09-04 23:12:29 |
| 合計ジャッジ時間 | 5,688 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge4_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | WA * 20 |
ソースコード
#include <immintrin.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#include <cstdint>
#include <cstdlib>
#include <vector>
using u128 = unsigned __int128;
#if defined(__GNUC__)
#define UNLIKELY(x) __builtin_expect(!!(x), 0)
#else
#define UNLIKELY(x) (x)
#endif
[[noreturn]]
static void fail() {
_exit(1);
}
static inline bool isDigit(char c) {
return static_cast<unsigned char>(c - '0') <= 9;
}
static uint32_t readUInt(
const char*& p,
const char* end,
uint32_t lo,
uint32_t hi
) {
if (UNLIKELY(p == end || !isDigit(*p))) {
fail();
}
uint32_t x = 0;
do {
uint32_t d =
static_cast<uint32_t>(*p - '0');
if (UNLIKELY(x > (hi - d) / 10)) {
fail();
}
x = x * 10 + d;
++p;
} while (p != end && isDigit(*p));
if (UNLIKELY(x < lo)) {
fail();
}
return x;
}
static inline void readSpace(
const char*& p,
const char* end
) {
if (UNLIKELY(p == end || *p != ' ')) {
fail();
}
++p;
}
static inline void readEoln(
const char*& p,
const char* end
) {
if (UNLIKELY(p == end)) {
fail();
}
if (*p == '\n') {
++p;
return;
}
if (
*p == '\r' &&
p + 1 != end &&
p[1] == '\n'
) {
p += 2;
return;
}
fail();
}
/*
A の制約:
0 <= A <= 1,000,000,000
各整数を uint32_t に変換するのではなく、
AVX-512 で 64 byte ずつ文字種を判定する。
leading zero も許容する。
000000000000001 -> OK
0001000000000 -> OK (= 1e9)
0001000000001 -> NG
という判定も正しく行う。
*/
__attribute__((
target("avx512f,avx512bw,bmi,bmi2,popcnt"),
optimize("O3", "unroll-loops"),
noinline
))
static void validateBody(
const char* p,
const char* end,
int H,
int W
) {
const __m512i C0 =
_mm512_set1_epi8('0');
const __m512i C1 =
_mm512_set1_epi8('1');
const __m512i C10 =
_mm512_set1_epi8(10);
const __m512i CSPACE =
_mm512_set1_epi8(' ');
const __m512i CLF =
_mm512_set1_epi8('\n');
const __m512i CCR =
_mm512_set1_epi8('\r');
const char* rowBegin = p;
uint64_t rowSpaces = 0;
uint64_t crTotal = 0;
uint64_t crUsed = 0;
int rows = 0;
/*
block 境界をまたぐ整数に対応するため、
直前 11 byte の情報を保持する。
*/
uint64_t prevDigit = 0;
uint64_t prevZero = 0;
uint64_t prevOne = 0;
bool prevSpace = false;
while (p < end) {
size_t rem =
static_cast<size_t>(end - p);
unsigned n =
rem >= 64
? 64
: static_cast<unsigned>(rem);
uint64_t laneMask =
n == 64
? ~0ULL
: ((1ULL << n) - 1);
__m512i v;
if (n == 64) {
v = _mm512_loadu_si512(
reinterpret_cast<const void*>(p)
);
} else {
v = _mm512_maskz_loadu_epi8(
static_cast<__mmask64>(laneMask),
p
);
}
/*
unsigned(c - '0') < 10
で digit 判定。
*/
__m512i sub =
_mm512_sub_epi8(v, C0);
uint64_t digit =
static_cast<uint64_t>(
_mm512_cmp_epu8_mask(
sub,
C10,
_MM_CMPINT_LT
)
) & laneMask;
uint64_t zero =
static_cast<uint64_t>(
_mm512_cmpeq_epi8_mask(v, C0)
) & laneMask;
uint64_t one =
static_cast<uint64_t>(
_mm512_cmpeq_epi8_mask(v, C1)
) & laneMask;
uint64_t space =
static_cast<uint64_t>(
_mm512_cmpeq_epi8_mask(
v,
CSPACE
)
) & laneMask;
uint64_t lf =
static_cast<uint64_t>(
_mm512_cmpeq_epi8_mask(
v,
CLF
)
) & laneMask;
uint64_t cr =
static_cast<uint64_t>(
_mm512_cmpeq_epi8_mask(
v,
CCR
)
) & laneMask;
uint64_t separators =
space | lf | cr;
/*
数字 / space / LF / CR
以外が含まれていたら NG。
*/
if (UNLIKELY(
(digit | separators) != laneMask
)) {
fail();
}
/*
連続した space は NG。
*/
if (UNLIKELY(
space & (space << 1)
)) {
fail();
}
/*
block 境界をまたぐ連続 space。
*/
if (UNLIKELY(
prevSpace && (space & 1)
)) {
fail();
}
/*
直前11文字 + 現在の64文字を
128-bit mask 上に並べる。
bit 0..10 : 前 block の末尾11文字
bit 11..74 : 現在の block
*/
u128 D =
(static_cast<u128>(digit) << 11)
| prevDigit;
u128 Z =
(static_cast<u128>(zero) << 11)
| prevZero;
u128 O =
(static_cast<u128>(one) << 11)
| prevOne;
u128 TERM =
static_cast<u128>(separators) << 11;
/*
delimiter の直前10文字が
全部数字かどうか。
*/
u128 last10digits =
(D << 1)
& (D << 2)
& (D << 3)
& (D << 4)
& (D << 5)
& (D << 6)
& (D << 7)
& (D << 8)
& (D << 9)
& (D << 10);
/*
delimiter の11文字前が non-zero で、
そこから delimiter まで11桁以上の
数字が続いていれば、必ず 1e9 超過。
leading zero はここでは無視されるため、
000000000000000001
のような値を誤って reject しない。
*/
u128 tooLarge11 =
TERM
& last10digits
& (
static_cast<u128>(D & ~Z)
<< 11
);
if (UNLIKELY(tooLarge11 != 0)) {
fail();
}
/*
delimiter 直前9文字が数字。
*/
u128 last9digits =
(D << 1)
& (D << 2)
& (D << 3)
& (D << 4)
& (D << 5)
& (D << 6)
& (D << 7)
& (D << 8)
& (D << 9);
/*
significant digits が10桁あるケース。
delimiter の10文字前が non-zero。
*/
u128 exactly10sig =
TERM
& last9digits
& (
static_cast<u128>(D & ~Z)
<< 10
);
if (UNLIKELY(exactly10sig != 0)) {
/*
1e9 以下で10 significant digits
なのは
1000000000
だけ。
*/
u128 last9zero =
(Z << 1)
& (Z << 2)
& (Z << 3)
& (Z << 4)
& (Z << 5)
& (Z << 6)
& (Z << 7)
& (Z << 8)
& (Z << 9);
u128 valid1e9 =
(O << 10)
& last9zero;
if (UNLIKELY(
exactly10sig & ~valid1e9
)) {
fail();
}
}
/*
CRLF validation 用。
*/
crTotal +=
static_cast<uint64_t>(
__builtin_popcountll(cr)
);
/*
行内の space 数を数える。
space は1個ずつ処理せず、
popcount だけで数える。
*/
uint64_t remainingSpace = space;
/*
LF だけは行境界なので処理する。
最大でも H <= 1,000,000 回。
*/
uint64_t nl = lf;
while (nl) {
unsigned k =
static_cast<unsigned>(
__builtin_ctzll(nl)
);
uint64_t lower =
k == 0
? 0
: ((1ULL << k) - 1);
rowSpaces +=
static_cast<uint64_t>(
__builtin_popcountll(
remainingSpace & lower
)
);
/*
すでに数えた space を消す。
*/
remainingSpace &= ~lower;
const char* lineEnd = p + k;
/*
1行に W 個の整数なら、
space は必ず W-1 個。
*/
if (UNLIKELY(
rowSpaces
!= static_cast<uint64_t>(W - 1)
)) {
fail();
}
/*
空行禁止。
*/
if (UNLIKELY(
rowBegin == lineEnd
)) {
fail();
}
const char* dataEnd = lineEnd;
/*
CRLF の CR を除外。
*/
if (
dataEnd > rowBegin &&
dataEnd[-1] == '\r'
) {
++crUsed;
--dataEnd;
}
/*
行頭・行末は数字でなければならない。
これにより
" 1 2"
"1 2 "
"1 2 \r\n"
なども reject する。
*/
if (UNLIKELY(
dataEnd == rowBegin
|| !isDigit(*rowBegin)
|| !isDigit(dataEnd[-1])
)) {
fail();
}
++rows;
if (UNLIKELY(rows > H)) {
fail();
}
rowBegin = lineEnd + 1;
rowSpaces = 0;
nl &= nl - 1;
}
/*
最後の LF より後の space を
次 block / 次 LF まで持ち越す。
*/
rowSpaces +=
static_cast<uint64_t>(
__builtin_popcountll(
remainingSpace
)
);
/*
次 block のために末尾11文字を保存。
*/
if (n == 64) {
prevDigit =
(digit >> 53) & 0x7FF;
prevZero =
(zero >> 53) & 0x7FF;
prevOne =
(one >> 53) & 0x7FF;
prevSpace =
((space >> 63) & 1) != 0;
} else {
prevSpace =
((space >> (n - 1)) & 1) != 0;
}
p += n;
}
/*
行数。
*/
if (UNLIKELY(rows != H)) {
fail();
}
/*
最終行にも EOL が必要。
EOL 後に余計な文字があっても NG。
*/
if (UNLIKELY(rowBegin != end)) {
fail();
}
/*
CR が存在するなら、すべて
CRLF の CR でなければならない。
*/
if (UNLIKELY(crTotal != crUsed)) {
fail();
}
}
static void validate(
const char* begin,
const char* end
) {
const char* p = begin;
int H =
static_cast<int>(
readUInt(
p,
end,
1,
1'000'000
)
);
readSpace(p, end);
int W =
static_cast<int>(
readUInt(
p,
end,
1,
4'000'000
)
);
if (UNLIKELY(
static_cast<int64_t>(H) * W
> 4'000'000
)) {
fail();
}
readEoln(p, end);
validateBody(
p,
end,
H,
W
);
}
int main() {
/*
stdin が通常ファイルなら mmap。
入力コピーを完全に省略する。
*/
struct stat st{};
if (
fstat(STDIN_FILENO, &st) == 0 &&
S_ISREG(st.st_mode)
) {
size_t size =
static_cast<size_t>(st.st_size);
if (size == 0) {
return 1;
}
void* mem =
mmap(
nullptr,
size,
PROT_READ,
MAP_PRIVATE,
STDIN_FILENO,
0
);
if (mem != MAP_FAILED) {
madvise(
mem,
size,
MADV_SEQUENTIAL
);
const char* begin =
static_cast<const char*>(mem);
validate(
begin,
begin + size
);
return 0;
}
}
/*
stdin が pipe 等で mmap できない場合。
*/
std::vector<char> buf;
buf.reserve(64ULL << 20);
constexpr size_t CHUNK = 1 << 20;
char tmp[CHUNK];
for (;;) {
ssize_t n =
read(
STDIN_FILENO,
tmp,
sizeof(tmp)
);
if (n < 0) {
return 1;
}
if (n == 0) {
break;
}
buf.insert(
buf.end(),
tmp,
tmp + n
);
}
if (buf.empty()) {
return 1;
}
validate(
buf.data(),
buf.data() + buf.size()
);
return 0;
}