結果

問題 No.1369 交換門松列・竹
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:01:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,946 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,804 KB
実行使用メモリ 134,828 KB
最終ジャッジ日時 2025-06-12 19:01:28
合計ジャッジ時間 6,604 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 8 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def is_monotriplet(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 is_valid_sequence(seq):
    n = len(seq)
    for i in range(n-2):
        a, b, c = seq[i], seq[i+1], seq[i+2]
        if not is_monotriplet(a, b, c):
            return False
    return True

def find_bad_triplets(seq):
    bad = []
    n = len(seq)
    for i in range(n-2):
        a, b, c = seq[i], seq[i+1], seq[i+2]
        if not is_monotriplet(a, b, c):
            bad.append(i)
    return bad

def solve_case(n, seq):
    bad_indices = find_bad_triplets(seq)
    if not bad_indices:
        return False
    # Collect all positions involved in bad triplets
    S = set()
    for i in bad_indices:
        S.add(i)
        S.add(i+1)
        S.add(i+2)
    # Now, for each possible swap (i,j) from S, check if it fixes everything
    S = list(S)
    for i in range(len(S)):
        for j in range(i+1, len(S)):
            pos_i = S[i]
            pos_j = S[j]
            if pos_i >= n or pos_j >= n:
                continue
            if seq[pos_i] == seq[pos_j]:
                continue
            # Create new sequence after swap
            new_seq = seq.copy()
            new_seq[pos_i], new_seq[pos_j] = new_seq[pos_j], new_seq[pos_i]
            # Check if new sequence is valid
            if is_valid_sequence(new_seq):
                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
        # Check if it's already valid
        if is_valid_sequence(A):
            print("No")
            continue
        # Check if any single swap can fix it
        possible = solve_case(N, A)
        print("Yes" if possible else "No")

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