結果

問題 No.5019 Hakai Project
ユーザー Kiri8128Kiri8128
提出日時 2023-11-18 00:25:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 115 ms / 3,000 ms
コード長 4,157 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 76,660 KB
スコア 476,009,408
最終ジャッジ日時 2023-11-18 00:25:16
合計ジャッジ時間 10,025 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 88 ms
76,660 KB
testcase_01 AC 86 ms
76,532 KB
testcase_02 AC 86 ms
76,660 KB
testcase_03 AC 106 ms
76,532 KB
testcase_04 AC 85 ms
76,532 KB
testcase_05 AC 84 ms
76,660 KB
testcase_06 AC 91 ms
76,532 KB
testcase_07 AC 88 ms
76,532 KB
testcase_08 AC 88 ms
76,532 KB
testcase_09 AC 87 ms
76,532 KB
testcase_10 AC 104 ms
76,532 KB
testcase_11 AC 90 ms
76,660 KB
testcase_12 AC 87 ms
76,660 KB
testcase_13 AC 85 ms
76,532 KB
testcase_14 AC 87 ms
76,660 KB
testcase_15 AC 88 ms
76,532 KB
testcase_16 AC 89 ms
76,532 KB
testcase_17 AC 109 ms
76,532 KB
testcase_18 AC 86 ms
76,532 KB
testcase_19 AC 86 ms
76,660 KB
testcase_20 AC 93 ms
76,532 KB
testcase_21 AC 90 ms
76,532 KB
testcase_22 AC 88 ms
76,532 KB
testcase_23 AC 89 ms
76,660 KB
testcase_24 AC 115 ms
76,532 KB
testcase_25 AC 91 ms
76,532 KB
testcase_26 AC 88 ms
76,532 KB
testcase_27 AC 89 ms
76,660 KB
testcase_28 AC 89 ms
76,532 KB
testcase_29 AC 98 ms
76,532 KB
testcase_30 AC 92 ms
76,532 KB
testcase_31 AC 105 ms
76,532 KB
testcase_32 AC 87 ms
76,532 KB
testcase_33 AC 87 ms
76,532 KB
testcase_34 AC 96 ms
76,532 KB
testcase_35 AC 97 ms
76,660 KB
testcase_36 AC 85 ms
76,532 KB
testcase_37 AC 89 ms
76,660 KB
testcase_38 AC 102 ms
76,536 KB
testcase_39 AC 93 ms
76,660 KB
testcase_40 AC 87 ms
76,660 KB
testcase_41 AC 90 ms
76,532 KB
testcase_42 AC 93 ms
76,532 KB
testcase_43 AC 88 ms
76,660 KB
testcase_44 AC 86 ms
76,532 KB
testcase_45 AC 111 ms
76,660 KB
testcase_46 AC 91 ms
76,532 KB
testcase_47 AC 90 ms
76,532 KB
testcase_48 AC 90 ms
76,532 KB
testcase_49 AC 90 ms
76,532 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def move(target_i, target_j):
    global cost
    global ANS
    global current_i, current_j
    b = sum(B)
    while (current_i, current_j) != (target_i, target_j):
        if current_i < target_i:
            ANS.append((1, "D"))
            current_i += 1
        elif current_i > target_i:
            ANS.append((1, "U"))
            current_i -= 1
        elif current_j < target_j:
            ANS.append((1, "R"))
            current_j += 1
        elif current_j > target_j:
            ANS.append((1, "L"))
            current_j -= 1
        cost += (1 if A[current_i][current_j] == "." else 2) * (b + 1) ** 2

def buy(k):
    global cost
    assert A[current_i][current_j] == "@"
    cost += price[k]
    B[k] += 1
    ANS.append((2, k + 1))
    if DEBUG:
        print("buy", k, "@", (current_i, current_j))

def bomb_check(k, ii, jj):
    s = 0
    t = 0
    for i, j in Z[k][1]:
        ni = ii + i
        nj = jj + j
        if 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".":
            if A[ni][nj] == "@":
                s += 1
            else:
                t += 1
    
def bomb(k):
    assert B[k] > 0
    global shop_list
    B[k] -= 1
    ANS.append((3, k + 1))
    for i, j in Z[k][1]:
        ni = current_i + i
        nj = current_j + j
        if 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".":
            if A[ni][nj] == "@":
                shop_list.remove((ni, nj))
            A[ni][nj] = "X"
    if DEBUG:
        print("bomb", k, "@", (current_i, current_j))

def answer():
    print(len(ANS))
    for a, b in ANS:
        print(a, b)
    
    if DEBUG:
        print("cost =", cost)
        writetext_output(ANS)

def disp():
    if DEBUG:
        print("")
        print("-" * 20)
        building_cnt = sum(a.count("#") for a in A)
        shop_cnt = sum(a.count("@") for a in A)
        print("building cnt =", building_cnt)
        print("shop cnt =", shop_cnt)
        print("shop_list =", len(shop_list), shop_list)
        print("cost =", cost)
        print("A =")
        for a in A:
            print("".join(a))
        print("-" * 20)
        print("")

try:
    LOCAL
except NameError:
    LOCAL = 0

if LOCAL:
    DEBUG = 1
    N, M, A, Z = random_testcase()
else:
    DEBUG = 0
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        A.append([a for a in input()])
    Z = []
    for _ in range(M):
        C, L = map(int, input().split())
        pos = []
        for _ in range(L):
            a, b = map(int, input().split())
            pos.append((a, b))
        Z.append((C, pos))
    
if DEBUG:
    writetext_input(N, M, A, Z)
price = []
B = [0] * M
cost = 0
current_i = 0
current_j = 0
ANS = []
if DEBUG:
    print("N =", N)
    print("M =", M)
shop_list = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == "@":
            shop_list.append((i, j))

disp()

for C, pos in Z:
    if DEBUG:
        print("C, cnt =", C, len(pos), "{:.4f}".format(len(pos) / C))
        print("pos =", pos)
    price.append(C)
    if 0:
        print("")
        print("C =", C)
        print("cnt =", len(pos))
    
    z = [["."] * 41 for _ in range(41)]
    for i, j in pos:
        z[i+20][j+20] = "#"
    if 0:
        print("pos =")
        for zz in z:
            print("".join(zz))

def best_shop(i, j):
    best_i = -1
    best_j = -1
    best = 1000
    for ti, tj in shop_list:
        d = abs(ti - i) + abs(tj - j)
        d += (max(10 - ti, 0) + max(ti - 39, 0) + max(10 - tj, 0) + max(tj - 39, 0)) * 5
        if 21 <= ti < 29:
            d += 15
        if 21 <= tj < 29:
            d += 15
        if d < best:
            best = d
            best_i = ti
            best_j = tj
    return best_i, best_j
    
while shop_list:
    move(*best_shop(current_i, current_j))
    ni = current_i + 1 if current_i < N - 1 else current_i - 1
    nj = current_j + 1 if current_j < N - 1 else current_j - 1
    for k in range(M):
        buy(k)
        buy(k)
        buy(k)
    for k in range(M):
        bomb(k)
    move(ni, current_j)
    for k in range(M):
        bomb(k)
    move(ni, nj)
    for k in range(M):
        bomb(k)
answer()
disp()
0