結果

問題 No.1369 交換門松列・竹
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:59:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,008 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 94,968 KB
最終ジャッジ日時 2025-06-12 14:00:45
合計ジャッジ時間 8,448 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 WA * 14 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def is_valid_triple(a, b, c):
    if a == b or b == c or a == c:
        return False
    mid = b
    return (mid > a and mid > c) or (mid < a and mid < c)

def is_valid_sequence(arr):
    n = len(arr)
    for i in range(n - 2):
        if not is_valid_triple(arr[i], arr[i+1], arr[i+2]):
            return False
    return True

def can_make_valid(arr):
    n = len(arr)
    problem_indices = []
    for i in range(n - 2):
        if not is_valid_triple(arr[i], arr[i+1], arr[i+2]):
            problem_indices.append(i)
    if not problem_indices:
        return True
    
    from copy import deepcopy
    for k in problem_indices:
        a, b, c = arr[k], arr[k+1], arr[k+2]
        for swap in [(k, k+1), (k, k+2), (k+1, k+2)]:
            i, j = swap
            if arr[i] == arr[j]:
                continue
            temp = deepcopy(arr)
            temp[i], temp[j] = temp[j], temp[i]
            affected = set()
            for pos in [i, j]:
                if pos >= 2:
                    affected.add(pos - 2)
                if pos <= n - 3:
                    affected.add(pos)
                if pos <= n - 3:
                    affected.add(pos + 1)
                if pos <= n - 3:
                    affected.add(pos + 2)
            valid = True
            for pos in affected:
                if pos >= 0 and pos <= n - 3:
                    x, y, z = temp[pos], temp[pos+1], temp[pos+2]
                    if not is_valid_triple(x, y, z):
                        valid = False
                        break
            if valid and is_valid_sequence(temp):
                return True
    return False

def main():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        N = int(input[ptr])
        ptr += 1
        A = list(map(int, input[ptr:ptr+N]))
        ptr += N
        if can_make_valid(A):
            print("Yes")
        else:
            print("No")

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