結果

問題 No.1369 交換門松列・竹
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:27:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,656 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 140,420 KB
最終ジャッジ日時 2025-03-20 20:28:47
合計ジャッジ時間 6,206 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

def solve():
    import sys
    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
        
        invalid_poses = []
        for i in range(N - 2):
            a, b, c = A[i], A[i+1], A[i+2]
            if not is_kadomatsu(a, b, c):
                invalid_poses.append(i)
        K = len(invalid_poses)
        if K > 4:
            print("No")
            continue
        
        candidate_pos = set()
        for pos in invalid_poses:
            for j in range(3):
                if pos + j < N:
                    candidate_pos.add(pos + j)
        
        positions = list(candidate_pos)
        candidates = set()
        for x in positions:
            for y in range(N):
                if x == y:
                    continue
                if A[x] == A[y]:
                    continue
                if x < y:
                    candidates.add((x, y))
                else:
                    candidates.add((y, x))
        
        for x in range(N):
            for y in positions:
                if x == y:
                    continue
                if A[x] == A[y]:
                    continue
                if x < y:
                    candidates.add((x, y))
                else:
                    candidates.add((y, x))
        
        found = False
        for x, y in candidates:
            if x >= N or y >= N:
                continue
            if A[x] == A[y]:
                continue
            A[x], A[y] = A[y], A[x]
            
            affected = set()
            for pos in [x-2, x-1, x]:
                if 0 <= pos <= N-3:
                    affected.add(pos)
            for pos in [y-2, y-1, y]:
                if 0 <= pos <= N-3:
                    affected.add(pos)
            for pos in invalid_poses:
                affected.add(pos)
            
            ok = True
            for pos in affected:
                if pos < 0 or pos > N-3:
                    continue
                a, b, c = A[pos], A[pos+1], A[pos+2]
                if not is_kadomatsu(a, b, c):
                    ok = False
                    break
            if ok:
                found = True
                A[x], A[y] = A[y], A[x]
                break
            A[x], A[y] = A[y], A[x]
        print("Yes" if found else "No")

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