結果

問題 No.3743 World Mapper
コンテスト
ユーザー Kurao
提出日時 2026-09-19 17:56:09
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 7,969 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 78 ms
コンパイル使用メモリ 83,584 KB
実行使用メモリ 77,952 KB
最終ジャッジ日時 2026-09-19 17:56:16
合計ジャッジ時間 5,125 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 4
部分点2 10 % AC * 9
部分点3 10 % AC * 9 RE * 5
部分点4 10 % AC * 9 RE * 10
部分点5 10 % AC * 9 RE * 15
部分点6 10 % AC * 9 RE * 20
部分点7 10 % AC * 9 RE * 25
部分点8 10 % AC * 9 RE * 30
部分点9 10 % AC * 9 RE * 35
満点 10 % AC * 9 RE * 40
合計 5 * 20% = 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from __future__ import annotations
import sys
sys.setrecursionlimit(2*10**7)
#↓codon===============================
import string
Alp_low=list(string.ascii_lowercase)
Alp_up=list(string.ascii_uppercase)
Digit="0123456789"
dij=[[0,1],[1,0],[0,-1],[-1,0]]
def nin():
    return list(map(int,input().split()))
def deq(x):
    return [i-1 for i in x]
mod=998244353
_factorial=[1]
def factorial(n):
    while len(_factorial)<=n:
        _factorial.append((_factorial[-1]*len(_factorial))%mod)
    return _factorial[n]

_inv_factorial=[1]
def inv_factorial(n):
    while len(_inv_factorial)<=n:
        _inv_factorial.append((_inv_factorial[-1]*pow(len(_inv_factorial),mod-2,mod))%mod)
    return _inv_factorial[n]

def binom(n,r):
    if r>=mod:
        raise ValueError("r is too big")
    if n<0:
        return 0
    if r>n:
        return 0
    if r<0:
        return 0
    ans=((factorial(n)*inv_factorial(r))%mod*inv_factorial(n-r))%mod
    return ans
def floyd_warshall(n, edges):
    dist = [[0 if i == j else float("inf") for i in range(n)] for j in range(n)]
    pred = [[None] * n for _ in range(n)]

    for u, v, d in edges:
        dist[u][v] = d
        pred[u][v] = u

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    pred[i][j] = pred[k][j]
    """Sanity Check
    for u, v, d in edges:
        if dist[u] + d < dist[v]:
            return None
    """

    return dist, pred

import random
random.seed(0)
def main():
    ans=[[], [], [[[286929], [132029]], [[116404, 258784]]], [[[10717, 158778], [268620, 88409], [183571, 62780]], [[75150, 150759, 124012], [282186, 148188, 106784]]], [[[156699, 82239, 256712], [273018, 166408, 276198], [90764, 241945, 288705], [146650, 174883, 27325]], [[38552, 38684, 25719, 198840], [72756, 231718, 191061, 40754], [26806, 19826, 221888, 98389]]], [[[105166, 92589, 205669, 172666], [294402, 75580, 274716, 3684], [285278, 233604, 268957, 200880], [153012, 295385, 70916, 95804], [16981, 53809, 177685, 64139]], [[135673, 196812, 58127, 148297, 137993], [162597, 16797, 171306, 25300, 237667], [121312, 280771, 215575, 300, 197077], [281670, 99161, 242113, 231217, 296148]]], [[[69481, 39452, 169450, 24760, 93987], [151813, 87817, 84750, 34663, 99059], [57776, 191712, 185113, 138649, 188935], [92849, 70433, 51684, 279830, 8736], [75459, 18593, 219468, 36103, 41524], [21597, 229954, 282028, 168756, 221746]], [[274181, 274115, 139589, 21649, 297417, 157728], [29792, 172328, 232134, 170860, 277598, 168666], [273026, 170791, 83795, 24869, 272623, 116305], [181126, 84542, 53359, 52495, 197307, 211316], [148170, 24282, 258560, 297883, 10229, 286094]]], [[[118467, 231748, 80051, 276679, 288360, 219780], [131728, 79939, 152752, 205906, 271356, 22165], [31794, 184936, 99732, 53619, 4263, 78632], [63664, 271690, 99003, 278120, 27300, 40558], [62914, 278679, 203539, 191174, 19893, 34567], [193356, 181218, 118425, 110747, 32013, 192996], [51988, 236619, 34422, 148891, 59986, 240406]], [[284596, 164236, 162872, 68644, 61722, 185910, 280881], [182391, 140275, 213224, 230199, 106604, 95460, 197310], [150904, 202262, 287102, 70686, 242729, 32432, 231761], [111312, 47565, 133498, 16774, 268440, 290324, 229511], [11985, 180633, 166860, 220340, 7026, 203841, 53040], [282255, 33319, 24843, 283376, 9633, 5687, 54824]]], [[[122656, 145292, 174810, 87082, 202908, 248397, 62635], [226885, 93284, 209545, 138369, 39535, 153679, 199595], [105740, 118337, 287412, 17893, 295256, 222739, 215836], [107686, 32042, 981, 296878, 230050, 240390, 38966], [83873, 28793, 143192, 98388, 46865, 132328, 223304], [139411, 40986, 92555, 59490, 138406, 270245, 133803], [117826, 63576, 55375, 58065, 233536, 117391, 68248], [296290, 52501, 108394, 15198, 248860, 205032, 218976]], [[186503, 38621, 215602, 105259, 146837, 129123, 148219, 151700], [155825, 152770, 16165, 87416, 250050, 13930, 61866, 6723], [146472, 2652, 164832, 222989, 21894, 248229, 119850, 1684], [10900, 199518, 78437, 205655, 85165, 66310, 254264, 180365], [53845, 135633, 235799, 116067, 98519, 208053, 135963, 41122], [232973, 164128, 35840, 52519, 103726, 117562, 275210, 152553], [241932, 271961, 137041, 184769, 13228, 8816, 203210, 22810]]], [[[185609, 191344, 82620, 159458, 146962, 289445, 246492, 299088], [73580, 79144, 45570, 298553, 143639, 206341, 111400, 199823], [83428, 71832, 27688, 241747, 279055, 55825, 117506, 190982], [36844, 152425, 144979, 298003, 109740, 55707, 58002, 152102], [23677, 161618, 216904, 124016, 81109, 21185, 5999, 148340], [101817, 754, 198348, 282821, 295214, 273732, 139828, 159833], [17301, 23191, 114320, 127538, 267998, 227523, 205655, 67769], [122140, 173, 135871, 84060, 150542, 121413, 280688, 119747], [283422, 184667, 238268, 190609, 88008, 145831, 170960, 110624]], [[132123, 68163, 103054, 91834, 201886, 263110, 145162, 249865, 236480], [102460, 266350, 52429, 64450, 95240, 6106, 147576, 269923, 230999], [218222, 5523, 142689, 161025, 51247, 278345, 230144, 98801, 172448], [8723, 128260, 271018, 137495, 3125, 177492, 18332, 36453, 213079], [237187, 226200, 173086, 197483, 59124, 134009, 170005, 236230, 249094], [247104, 55811, 86031, 263428, 264770, 131586, 231333, 230580, 82690], [10299, 102868, 206533, 115175, 207080, 262630, 265240, 82592, 150406], [173029, 201596, 203900, 217465, 42715, 217859, 134945, 234851, 264149]]], [[[262771, 221771, 175628, 282498, 72816, 59754, 287962, 216006, 149938], [27989, 288520, 71733, 176222, 240436, 214408, 150631, 194872, 65746], [117910, 214425, 68052, 131240, 54652, 75893, 263766, 159985, 10072], [134983, 37675, 181342, 70329, 276493, 229994, 227619, 25418, 139184], [78370, 120350, 169324, 89174, 160396, 222873, 17230, 268064, 126244], [8339, 78511, 92302, 180783, 138489, 219154, 239629, 175898, 263254], [121052, 267062, 68596, 299197, 167490, 14073, 114961, 10218, 128664], [55981, 132465, 289368, 150258, 231429, 120954, 136913, 54307, 44269], [223, 30156, 12416, 133526, 231337, 153390, 168435, 5002, 76493], [109987, 72681, 238668, 267869, 76709, 265372, 214742, 76273, 82496]], [[81020, 9346, 153195, 191072, 263810, 14185, 241679, 103137, 9926, 140645], [283671, 99754, 277139, 213519, 282497, 128028, 230217, 61205, 84586, 74163], [40241, 221371, 117390, 139901, 155792, 216221, 100568, 145001, 70100, 139860], [102368, 274307, 146461, 38146, 283779, 157345, 216380, 52583, 123909, 102313], [652, 101476, 161932, 81926, 172222, 56868, 173429, 154256, 136750, 62759], [153963, 58289, 8018, 91524, 287343, 123491, 46883, 18823, 6939, 36701], [146672, 214409, 43255, 158229, 46257, 137634, 164539, 19241, 84621, 5779], [51983, 269456, 211170, 196994, 291669, 132953, 116510, 113236, 14876, 162633], [22844, 176617, 82922, 86373, 35730, 166002, 104660, 267783, 78593, 263542]]]]
    n,=nin()
    for i in ans[n][1]:
        print(*i)
    for i in ans[n][0]:
        print(*i)
    return
    

    ans=[[],[]]
    use=[i for i in range(1,3*10**5) if i.bit_count()<=10]
    for n in range(2,11):
        while True:
            g=[]
            v=[[] for _ in range(n)]
            h=[[] for _ in range(n-1)]
            for i in range(n):
                for j in range(n):
                    for di,dj in [(0,1),(1,0)]:
                        if 0<=i+di<n and 0<=j+dj<n:
                            #w=random.randint(1,3*10**5)
                            w=random.choice(use)
                            if di==0:
                                v[i].append(w)
                            else:
                                h[i].append(w)
                            g.append((i*n+j,(i+di)*n+(j+dj),w))
                            g.append(((i+di)*n+(j+dj),i*n+j,w))
            d=set(sum(floyd_warshall(n**2,g)[0],[]))
            if len(d)==n**2*(n**2-1)//2+1:
                ans.append([v,h])
                break
    print(ans)

if __name__=="__main__":
    main()
0