#1061769 (PyPy3) No.1369 交換門松列・竹

• 問題: No.1369 交換門松列・竹
• ユーザー: lam6er
• 提出日時: 2025-03-31 17:32:26
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 3,304 bytes
• コンパイル時間: 222 ms
• コンパイル使用メモリ: 82,552 KB
• 実行使用メモリ: 90,416 KB
• 最終ジャッジ日時: 2025-03-31 17:33:27
• 合計ジャッジ時間: 9,452 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 1
other	AC * 21 WA * 8 TLE * 2 -- * 2

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
def is_kadomatsu(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 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
        
        BAD = []
        for s in range(N-2):
            a = A[s]
            b = A[s+1]
            c = A[s+2]
            if not is_kadomatsu(a, b, c):
                BAD.append(s)
        
        # If no BAD, which is impossible
        if not BAD:
            print("No")
            continue
        
        # Collect all positions in BAD triplets
        S = set()
        for s in BAD:
            S.add(s)
            S.add(s+1)
            S.add(s+2)
        S = list(S)
        possible = False
        
        # Iterate all possible pairs in S
        for i_idx in range(len(S)):
            i = S[i_idx]
            for j_idx in range(i_idx+1, len(S)):
                j = S[j_idx]
                if A[i] == A[j]:
                    continue
                
                # Check if all BAD triplets include i or j
                all_included = True
                for s in BAD:
                    triplet_includes = False
                    for pos in [s, s+1, s+2]:
                        if pos == i or pos == j:
                            triplet_includes = True
                            break
                    if not triplet_includes:
                        all_included = False
                        break
                if not all_included:
                    continue
                
                # Perform swap and check
                A[i], A[j] = A[j], A[i]
                
                # Check BAD triplets are now valid
                valid_bad = True
                for s in BAD:
                    a_vals = A[s]
                    b_vals = A[s+1]
                    c_vals = A[s+2]
                    if not is_kadomatsu(a_vals, b_vals, c_vals):
                        valid_bad = False
                        break
                if not valid_bad:
                    A[i], A[j] = A[j], A[i]
                    continue
                
                # Check all triplets involving i or j's positions
                valid = True
                checked = set()
                for x in [i, j]:
                    for s in [x-2, x-1, x]:
                        if s <0 or s+2 >= N:
                            continue
                        if s not in checked:
                            checked.add(s)
                            a = A[s]
                            b = A[s+1]
                            c = A[s+2]
                            if not is_kadomatsu(a, b, c):
                                valid = False
                                break
                    if not valid:
                        break
                # Revert swap
                A[i], A[j] = A[j], A[i]
                
                if valid:
                    possible = True
                    break
            if possible:
                break
        
        print("Yes" if possible else "No")
if __name__ == "__main__":
    solve()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX