結果
| 問題 | No.3677 Global Checksum |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-09-03 16:14:51 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,371 bytes |
| 記録 | |
| コンパイル時間 | 1,452 ms |
| コンパイル使用メモリ | 210,320 KB |
| 実行使用メモリ | 30,080 KB |
| 最終ジャッジ日時 | 2026-09-04 23:12:12 |
| 合計ジャッジ時間 | 4,272 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge6_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | WA * 12 TLE * 1 -- * 7 |
ソースコード
#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)
#define TARGET_AVX512 \
__attribute__((target("avx512f,avx512bw,bmi,bmi2,popcnt")))
#else
#define UNLIKELY(x) (x)
#define TARGET_AVX512
#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 void readSpace(
const char*& p,
const char* end
) {
if (UNLIKELY(p == end || *p != ' ')) {
fail();
}
++p;
}
static 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 <= 1000000000
数値変換はしない。
token が
0～9桁 -> OK
10桁 -> 先頭 0、または 1000000000
11桁～ -> NG
10桁判定も 64 個まとめて bit 演算する。
*/
TARGET_AVX512
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;
/*
直前 11 byte 分を保持。
bit 0..10:
現在の 64 byte 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;
if (n == 64) {
laneMask = ~0ULL;
} else {
laneMask = (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
);
}
/*
digit 判定。
unsigned(v - '0') < 10
*/
__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;
/*
数字 / ' ' / '\n' / '\r'
以外は即 NG
*/
if (UNLIKELY(
(digit | separators) != laneMask
)) {
fail();
}
/*
連続スペースは NG。
"1 2"
*/
if (UNLIKELY(space & (space << 1))) {
fail();
}
if (UNLIKELY(
prevSpace && (space & 1)
)) {
fail();
}
/*
------------------------------
A <= 1,000,000,000 の SIMD 検査
------------------------------
*/
/*
直前11 byte + 現在64 byte
= 75 bit
*/
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 ten =
(D << 1)
& (D << 2)
& (D << 3)
& (D << 4)
& (D << 5)
& (D << 6)
& (D << 7)
& (D << 8)
& (D << 9)
& (D << 10);
/*
直前11文字も数字なら
11桁以上なので NG。
*/
u128 tooLong =
TERM
& ten
& (D << 11);
if (UNLIKELY(tooLong != 0)) {
fail();
}
/*
ちょうど10桁の token。
*/
u128 exactly10 =
TERM
& ten
& ~(D << 11);
if (exactly10 != 0) {
/*
token の後ろ9桁が
すべて '0'
*/
u128 nineZero =
(Z << 1)
& (Z << 2)
& (Z << 3)
& (Z << 4)
& (Z << 5)
& (Z << 6)
& (Z << 7)
& (Z << 8)
& (Z << 9);
/*
10桁で valid なのは
0xxxxxxxxx
または
1000000000
先頭 0 なら数値として
1e9 未満なので OK。
*/
u128 valid10 =
(Z << 10)
|
(
(O << 10)
& nineZero
);
if (UNLIKELY(
exactly10 & ~valid10
)) {
fail();
}
}
/*
CR の総数だけ数えておく。
LF 処理時に CRLF として
使用された CR の数と比較する。
*/
crTotal +=
static_cast<uint64_t>(
__builtin_popcountll(cr)
);
/*
------------------------------
行構造の検査
------------------------------
space 自体は popcount するだけ。
1個ずつ処理しない。
LF だけ scalar で処理する。
*/
uint64_t remainingSpace = space;
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
)
);
remainingSpace &= ~lower;
const char* lineEnd = p + k;
/*
この行に W-1 個の空白が
ちょうど存在する必要がある。
*/
if (UNLIKELY(
rowSpaces
!= static_cast<uint64_t>(W - 1)
)) {
fail();
}
/*
空行禁止。
*/
if (UNLIKELY(
rowBegin == lineEnd
)) {
fail();
}
const char* dataEnd = lineEnd;
/*
CRLF
*/
if (
dataEnd > rowBegin &&
dataEnd[-1] == '\r'
) {
++crUsed;
--dataEnd;
}
/*
行の先頭・末尾は数字。
*/
if (UNLIKELY(
dataEnd == rowBegin
|| !isDigit(*rowBegin)
|| !isDigit(dataEnd[-1])
)) {
fail();
}
++rows;
if (UNLIKELY(rows > H)) {
fail();
}
rowBegin = lineEnd + 1;
rowSpaces = 0;
nl &= nl - 1;
}
/*
block の最後の LF より後にある
space を次 block に持ち越す。
*/
rowSpaces +=
static_cast<uint64_t>(
__builtin_popcountll(
remainingSpace
)
);
/*
末尾11byteを次 block に渡す。
*/
if (n == 64) {
prevDigit =
(digit >> 53) & 0x7FF;
prevZero =
(zero >> 53) & 0x7FF;
prevOne =
(one >> 53) & 0x7FF;
prevSpace =
((space >> 63) & 1) != 0;
} else {
/*
最終 block なので
実際には次回使用されない。
*/
prevSpace =
((space >> (n - 1)) & 1) != 0;
}
p += n;
}
/*
行数が H でなければ NG。
*/
if (UNLIKELY(rows != H)) {
fail();
}
/*
最終行には必ず EOL が必要。
*/
if (UNLIKELY(rowBegin != end)) {
fail();
}
/*
全 CR が CRLF の一部である必要がある。
*/
if (UNLIKELY(crTotal != crUsed)) {
fail();
}
}
int main() {
struct stat st;
if (
fstat(STDIN_FILENO, &st) != 0 ||
!S_ISREG(st.st_mode)
) {
/*
pipe fallback
*/
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;
}
const char* p = buf.data();
const char* end = p + buf.size();
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
);
return 0;
}
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) {
return 1;
}
/*
sequential access のヒント。
*/
madvise(
mem,
size,
MADV_SEQUENTIAL
);
const char* p =
static_cast<const char*>(mem);
const char* end =
p + size;
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
);
return 0;
}