結果
問題 | No.2689 Populous |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2024-02-24 05:31:32 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,189 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 165,132 KB |
最終ジャッジ日時 | 2024-02-24 05:37:29 |
合計ジャッジ時間 | 14,225 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge16 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
55,600 KB |
testcase_01 | AC | 45 ms
55,600 KB |
testcase_02 | AC | 45 ms
55,600 KB |
testcase_03 | AC | 60 ms
66,112 KB |
testcase_04 | AC | 69 ms
68,492 KB |
testcase_05 | AC | 58 ms
63,768 KB |
testcase_06 | AC | 251 ms
77,700 KB |
testcase_07 | AC | 462 ms
78,148 KB |
testcase_08 | AC | 666 ms
78,456 KB |
testcase_09 | AC | 46 ms
55,600 KB |
testcase_10 | AC | 61 ms
66,112 KB |
testcase_11 | AC | 47 ms
55,600 KB |
testcase_12 | AC | 84 ms
74,840 KB |
testcase_13 | AC | 56 ms
64,164 KB |
testcase_14 | AC | 132 ms
77,104 KB |
testcase_15 | AC | 58 ms
66,276 KB |
testcase_16 | AC | 139 ms
77,216 KB |
testcase_17 | AC | 54 ms
64,172 KB |
testcase_18 | AC | 177 ms
77,732 KB |
testcase_19 | AC | 250 ms
77,412 KB |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
ソースコード
""" 愚直 """ import sys from collections import deque import itertools import heapq def exist(A): q = [] #print (A) for i in range(H): for j in range(W): if A[i][j] != None and A[i][j] >= 0: heapq.heappush( q , (A[i][j],i,j) ) if A[i][j] == None: A[i][j] = float("inf") while q: cost,i,j = heapq.heappop(q) if cost != A[i][j]: continue for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)): if 0 <= x < H and 0 <= y < W: if A[x][y] > A[i][j] + 1: A[x][y] = A[i][j] + 1 heapq.heappush( q, (A[x][y],x,y) ) if x==0 or x==H-1 or y==0 or y==W-1: return False return True import sys mod = 998244353 H,W = map(int,input().split()) assert 3 <= H <= 1000 assert 3 <= W <= 1000 A = [[None] * W for i in range(H)] # input A[0] = list(map(int,input().split())) for i in range(1,H-1): A[i][0],A[i][-1] = map(int,input().split()) A[-1] = list(map(int,input().split())) for i in range(H): for j in range(W): if A[i][j] != None: assert 1 <= A[i][j] <= 2000 flag = True for i in range(H): for j in range(W): if A[i][j] == None: continue for i2,j2 in ( (i+1,j),(i,j+1) ): if i2 < H and j2 < W and A[i2][j2] != None: if abs(A[i][j] - A[i2][j2]) > 1: flag = False if not flag: print (-1) sys.exit() yoko = [] tate = [] last = False for i in range(H): diff = abs(A[i][0] - A[i][-1]) if diff > W-1: yoko.append(i) for j in range(W): diff = abs(A[0][j] - A[-1][j]) if diff > H-1: tate.append(j) if tate: A = [[ A[i][j] for i in range(H) ] for j in range(W)] H,W = W,H yoko,tate = tate,yoko ans = 0 for bits in range((W-2)**len(yoko)): js = [] for mmm in range(len(yoko)): js.append( bits % (W-2) + 1 ) bits //= W-2 B = [[ A[i][j] for j in range(W) ] for i in range(H)] for i,j in zip(yoko,js): B[i][j] = -1 if exist(B): ans += 1 print (ans)