結果

問題 No.1369 交換門松列・竹
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:40:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,120 bytes
コンパイル時間 460 ms
コンパイル使用メモリ 81,644 KB
実行使用メモリ 79,932 KB
最終ジャッジ日時 2025-04-16 15:45:01
合計ジャッジ時間 3,269 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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

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
        
        B = []
        for k in range(N - 2):
            a, b, c = A[k], A[k+1], A[k+2]
            if not is_valid(a, b, c):
                B.append(k)
        
        if len(B) > 20:
            print("No")
            continue
        
        S = set()
        for k in B:
            S.add(k)
            S.add(k+1)
            S.add(k+2)
        S = sorted(S)
        found = False
        
        for i in range(len(S)):
            for j in range(i + 1, len(S)):
                x = S[i]
                y = S[j]
                if A[x] == A[y]:
                    continue
                
                A[x], A[y] = A[y], A[x]
                
                valid = True
                for k in B:
                    a, b, c = A[k], A[k+1], A[k+2]
                    if not is_valid(a, b, c):
                        valid = False
                        break
                if not valid:
                    A[x], A[y] = A[y], A[x]
                    continue
                
                for xx in [x, y]:
                    for start in [xx - 2, xx - 1, xx]:
                        if start < 0 or start + 2 >= N:
                            continue
                        a, b, c = A[start], A[start+1], A[start+2]
                        if not is_valid(a, b, c):
                            valid = False
                            break
                    if not valid:
                        break
                if valid:
                    found = True
                
                A[x], A[y] = A[y], A[x]
                if found:
                    break
            if found:
                break
        
        print("Yes" if found else "No")

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