結果

問題 No.3743 World Mapper
コンテスト
ユーザー 👑 kencho
提出日時 2026-09-03 04:55:02
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 709 ms / 2,000 ms
+ 532µs
コード長 1,503 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 60 ms
コンパイル使用メモリ 15,232 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2026-09-19 13:05:05
合計ジャッジ時間 17,807 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 4
部分点2 10 % AC * 9
部分点3 10 % AC * 14
部分点4 10 % AC * 19
部分点5 10 % AC * 24
部分点6 10 % AC * 29
部分点7 10 % AC * 34
部分点8 10 % AC * 39
部分点9 10 % AC * 44
満点 10 % AC * 49
合計 5 * 100% = 500 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def prime(x):
    if x < 2: return False
    d = 2
    while d * d <= x:
        if x % d == 0: return False
        d += 1
    return True

def factors(x):
    result, d = [], 2
    while d * d <= x:
        if x % d == 0:
            result.append(d)
            while x % d == 0: x //= d
        d += 1
    if x > 1: result.append(x)
    return result

n = int(sys.stdin.buffer.readline()); size = n * n
p = size + 1
while not prime(p): p += 1
fs = factors(p - 1)
g = next(x for x in range(2, p) if all(pow(x, (p - 1) // q, p) != 1 for q in fs))
mod, power, marks = p * (p - 1), 1, []
for i in range(p - 1):
    marks.append((p * i + (p - 1) * power) % mod)
    power = power * g % p
marks.sort(); ext = marks + [x + mod for x in marks]
def pos(r, c): return r * n + (c if r % 2 == 0 else n - 1 - c)
edges = [(pos(r, c), pos(r + 1, c)) for r in range(n - 1) for c in range(n)] + [(pos(r, c), pos(r, c + 1)) for r in range(n) for c in range(n - 1)]
best, start = 10**30, 0
for s in range(p - 1):
    maximum = 0
    for u, v in edges:
        maximum = max(maximum, abs(ext[s + u] - ext[s + v]))
        if maximum >= best: break
    if maximum < best: best, start = maximum, s
mark = [ext[start + i] - ext[start] for i in range(size)]
out = []
for r in range(n - 1): out.append(" ".join(str(abs(mark[pos(r, c)] - mark[pos(r + 1, c)])) for c in range(n)))
for r in range(n): out.append(" ".join(str(abs(mark[pos(r, c)] - mark[pos(r, c + 1)])) for c in range(n - 1)))
print("\n".join(out))
0