結果

問題 No.1888 Odd Insertion
ユーザー gew1fw
提出日時 2025-06-12 18:20:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,606 bytes
コンパイル時間 492 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 120,704 KB
最終ジャッジ日時 2025-06-12 18:21:23
合計ジャッジ時間 12,989 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, size):
        self.n = size
        self.size_tree = 1
        while self.size_tree < self.n:
            self.size_tree <<= 1
        self.tree = [0] * (2 * self.size_tree)
        # Initialize leaves
        for i in range(self.n):
            self.tree[self.size_tree + i] = 1
        # Build the tree
        for i in range(self.size_tree - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def find_kth(self, k):
        idx = 1
        while idx < self.size_tree:
            left = 2 * idx
            right = left + 1
            if self.tree[left] > k:
                idx = left
            else:
                k -= self.tree[left]
                idx = right
        return idx - self.size_tree

    def delete(self, pos):
        idx = self.size_tree + pos
        if self.tree[idx] == 0:
            return False
        self.tree[idx] = 0
        idx >>= 1
        while idx >= 1:
            self.tree[idx] = self.tree[2*idx] + self.tree[2*idx+1]
            idx >>= 1
        return True

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    P = list(map(int, input[1:N+1]))
    
    st = SegmentTree(N)
    x_list = []
    y_list = []
    possible = True
    
    for i in range(N, 0, -1):
        if i % 2 == 1:
            current_k = i - 1  # 0-based
        else:
            current_k = i - 2
        # Check if current_k is within the possible range
        if current_k < 0 or current_k >= i:
            possible = False
            break
        # Check if there are enough elements
        if st.tree[1] < (current_k + 1):
            possible = False
            break
        # Find the k-th element
        original_pos = st.find_kth(current_k)
        x = P[original_pos]
        x_list.append(x)
        y_list.append(current_k + 1)  # Convert to 1-based
        # Delete the element
        st.delete(original_pos)
    
    if not possible:
        print("No")
        return
    
    # Check if each x is one of the two smallest in its set
    min1 = float('inf')
    min2 = float('inf')
    valid = True
    for x in x_list:
        if x < min1:
            min2 = min1
            min1 = x
        elif x < min2:
            min2 = x
        if x != min1 and x != min2:
            valid = False
            break
    if not valid:
        print("No")
        return
    
    # Prepare the answer
    x_list = x_list[::-1]
    y_list = y_list[::-1]
    print("Yes")
    for x, y in zip(x_list, y_list):
        print(x, y)

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