結果

問題 No.2743 Twisted Lattice
ユーザー tcltktcltk
提出日時 2024-04-28 16:51:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,450 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 82,544 KB
実行使用メモリ 220,800 KB
最終ジャッジ日時 2024-11-17 10:35:41
合計ジャッジ時間 12,441 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,274 ms
188,272 KB
testcase_01 AC 713 ms
154,980 KB
testcase_02 AC 498 ms
168,576 KB
testcase_03 WA -
testcase_04 AC 1,278 ms
220,800 KB
testcase_05 AC 1,283 ms
219,896 KB
testcase_06 AC 1,296 ms
220,240 KB
testcase_07 AC 1,318 ms
219,912 KB
testcase_08 AC 131 ms
86,848 KB
testcase_09 AC 133 ms
87,148 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/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

    Y1 = list(set(Y))
    Y1.sort()

    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 Y1:
        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 Y1:
        if i0 == -1:
            x0 = Line[y][0]
            i0 = dic[(x0, y)]
            continue
        x0, y0 = X[i0], Y[i0]
        if y0 == y:
            continue
        for x in Line[y]:
            cost = (x-1) + (x0-1) + (y-y0)
            i = dic[(x, y)]
            Ans[i] = min(Ans[i], cost)
        if Line[y][0]-y < x0-y0:
            i0 = i

    i0 = -1
    for y in reversed(Y1):
        if i0 == -1:
            x0 = Line[y][0]
            i0 = dic[(x0, y)]
            continue
        x0, y0 = X[i0], Y[i0]
        if y0 == y:
            continue
        for x in Line[y]:
            cost = (x-1) + (x0-1) + (y0-y)
            i = dic[(x, y)]
            Ans[i] = min(Ans[i], cost)
        if Line[y][0]+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)
0