結果
問題 | No.2743 Twisted Lattice |
ユーザー | tcltk |
提出日時 | 2024-04-28 15:42:30 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,435 bytes |
コンパイル時間 | 375 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 262,088 KB |
最終ジャッジ日時 | 2024-11-17 09:08:07 |
合計ジャッジ時間 | 17,111 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,035 ms
188,492 KB |
testcase_01 | TLE | - |
testcase_02 | TLE | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 131 ms
86,864 KB |
testcase_09 | AC | 130 ms
262,088 KB |
ソースコード
#!/usr/bin/env python3 # from typing import * import sys import io import math import collections import decimal import itertools import bisect import heapq import random def input(): return sys.stdin.readline()[:-1] # sys.setrecursionlimit(1000000) # _INPUT = """10 10 6 # 1 2 # 2 3 # 3 3 # 10 7 # 8 2 # 3 5 # """ # sys.stdin = io.StringIO(_INPUT) INF = 10**18 YES = 'Yes' NO = 'No' def solve(H, W, N, X, Y): dic = dict() for i in range(N): dic[(X[i], Y[i])] = i Ans = [INF] * N Line = collections.defaultdict(list) for i in range(N): Line[Y[i]].append(X[i]) for l in Line.values(): l.sort() for y in range(N): for k in range(len(Line[y])): x = Line[y][k] i = dic[(x, y)] if 0 <= k-1: x1 = Line[y][k-1] Ans[i] = min(Ans[i], x-x1) if k+1 < len(Line[y]): x2 = Line[y][k+1] Ans[i] = min(Ans[i], x2-x) for i in range(N): x, y = X[i], Y[i] for y1 in [y-1, y+1]: if y1 in Line: k = bisect.bisect_left(Line[y1], x) if 0 <= k-1: x1 = Line[y1][k-1] Ans[i] = min(Ans[i], x) #x1 + (x-x1) if k < len(Line[y1]): x2 = Line[y1][k] Ans[i] = min(Ans[i], x2) # x + (x2-x) i0 = -1 for y in sorted(Y): if i0 == -1: x0 = Line[y][0] i0 = dic[(x0, y)] continue x0, y0 = X[i0], Y[i0] for x in Line[y]: if y0 == y: continue cost = (x-1) + (x0-1) + (y-y0) i = dic[(x, y)] Ans[i] = min(Ans[i], cost) if x-y < x0-y0: i0 = i i0 = -1 for y in sorted(Y, reverse=True): if i0 == -1: x0 = Line[y][0] i0 = dic[(x0, y)] continue x0, y0 = X[i0], Y[i0] for x in Line[y]: if y0 == y: continue cost = (x-1) + (x0-1) + (y0-y) i = dic[(x, y)] Ans[i] = min(Ans[i], cost) if x+y < x0+y0: i0 = i return Ans H, W, N = map(int, input().split()) X, Y = [], [] for _ in range(N): x, y = map(int, input().split()) X.append(x) Y.append(y) ans = solve(H, W, N, X, Y) for v in ans: print(v)