結果

問題 No.1508 Avoid being hit
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-09-16 01:35:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 201 ms / 3,000 ms
コード長 3,342 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 81,960 KB
実行使用メモリ 102,408 KB
最終ジャッジ日時 2024-09-16 01:35:12
合計ジャッジ時間 7,743 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
96,216 KB
testcase_01 AC 37 ms
53,184 KB
testcase_02 AC 37 ms
52,640 KB
testcase_03 AC 36 ms
52,820 KB
testcase_04 AC 38 ms
52,696 KB
testcase_05 AC 38 ms
52,988 KB
testcase_06 AC 37 ms
52,460 KB
testcase_07 AC 38 ms
53,192 KB
testcase_08 AC 38 ms
54,540 KB
testcase_09 AC 37 ms
52,688 KB
testcase_10 AC 36 ms
52,836 KB
testcase_11 AC 36 ms
53,768 KB
testcase_12 AC 36 ms
53,560 KB
testcase_13 AC 36 ms
52,984 KB
testcase_14 AC 36 ms
52,964 KB
testcase_15 AC 37 ms
52,604 KB
testcase_16 AC 88 ms
98,520 KB
testcase_17 AC 75 ms
89,004 KB
testcase_18 AC 68 ms
83,116 KB
testcase_19 AC 84 ms
95,572 KB
testcase_20 AC 93 ms
102,408 KB
testcase_21 AC 83 ms
93,732 KB
testcase_22 AC 91 ms
99,020 KB
testcase_23 AC 90 ms
98,760 KB
testcase_24 AC 201 ms
101,124 KB
testcase_25 AC 182 ms
97,724 KB
testcase_26 AC 100 ms
77,424 KB
testcase_27 AC 157 ms
86,104 KB
testcase_28 AC 170 ms
85,020 KB
testcase_29 AC 184 ms
97,784 KB
testcase_30 AC 162 ms
87,412 KB
testcase_31 AC 178 ms
95,280 KB
testcase_32 AC 180 ms
97,604 KB
testcase_33 AC 125 ms
80,720 KB
testcase_34 AC 107 ms
93,808 KB
testcase_35 AC 66 ms
74,892 KB
testcase_36 AC 86 ms
87,268 KB
testcase_37 AC 75 ms
78,436 KB
testcase_38 AC 102 ms
89,712 KB
testcase_39 AC 92 ms
88,060 KB
testcase_40 AC 115 ms
96,068 KB
testcase_41 AC 89 ms
88,236 KB
testcase_42 AC 113 ms
96,452 KB
testcase_43 AC 121 ms
98,920 KB
testcase_44 AC 37 ms
54,224 KB
testcase_45 AC 36 ms
53,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1508

def main():
    N, Q = map(int ,input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))


    win_flag = [0, N - 1]
    win_flag_list = []
    win_flag_list.append(win_flag)
    for q in reversed(range(Q)):
        # 遭難者が叩く
        a = A[q] - 1
        b = B[q] - 1

        new_win_flag = [0, N - 1]
        if (a, b) in ((win_flag[0], win_flag[0] + 1), (win_flag[0] + 1, win_flag[0])):
            new_win_flag[0] = win_flag[0] + 1
        elif a == win_flag[0] or b == win_flag[0]:
            new_win_flag[0] = win_flag[0]
        else:
            new_win_flag[0] = max(0, win_flag[0] - 1)

        if (a, b) in ((win_flag[1], win_flag[1] - 1), (win_flag[1] - 1, win_flag[1])):
            new_win_flag[1] = win_flag[1] - 1
        elif a == win_flag[1] or b == win_flag[1]:
            new_win_flag[1] = win_flag[1]
        else:
            new_win_flag[1] = min(N - 1, win_flag[1] + 1)

        win_flag = new_win_flag
        win_flag_list.append(win_flag)
        if win_flag[0] > win_flag[1]:
            print("NO")
            return
    
    win_flag_list.reverse()
    print("YES")
    actions = []
    for i in range(N):
        if win_flag_list[0][0] <= i <= win_flag_list[0][1]:
            actions.append(i + 1)

            i0 = i
            for q in range(Q):
                a = A[q] - 1
                b = B[q] - 1
                for j in range(-1, 2):
                    if 0 <= i0 + j < N:
                        x0, y0 = win_flag_list[q + 1]
                        if x0 <= i0 + j <= y0 and (i0 + j) not in (a, b):
                            actions.append(i0 + j + 1)
                            i0 = i0 + j
                            break
            break
    for a in actions:
        print(str(a))




def main2():
    N, Q = map(int ,input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))


    win_flag = [1] * N
    win_flag_list = []
    win_flag_list.append(win_flag)
    for q in reversed(range(Q)):
        # 遭難者が叩く
        a = A[q] - 1
        b = B[q] - 1
        win_flag[a] = 0
        win_flag[b] = 0

        # あなたが今いる駒が勝てそうかどうかの判定
        new_win_flag = [-1] * N
        for i in range(N):
            is_win = 0
            for j in range(-1, 2):
                if 0 <= i + j < N:
                    is_win |= win_flag[i + j]
            new_win_flag[i] = is_win
        win_flag = new_win_flag
        win_flag_list.append(win_flag)
    
        if sum(win_flag) <= 0:
            print("NO")
            return
    
    win_flag_list.reverse()

    print("YES")
    actions = []
    for i in range(N):
        if win_flag_list[0][i] == 1:
            actions.append(i + 1)

            i0 = i
            for q in range(Q):
                a = A[q] - 1
                b = B[q] - 1
                for j in range(-1, 2):
                    if 0 <= i0 + j < N:
                        if win_flag_list[q + 1][i0 + j] == 1 and (i0 + j) not in (a, b):
                            actions.append(i0 + j + 1)
                            i0 = i0 + j
                            break
            break
    for a in actions:
        print(str(a))




        



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