結果

問題 No.1786 Maximum Suffix Median (Online)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:11:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,420 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 61,312 KB
最終ジャッジ日時 2025-06-12 21:13:25
合計ジャッジ時間 7,140 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    A_prime = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    
    ans = [0]*(N+1)  # ans[0] is dummy
    res = []
    
    A = [0]*(N+1)
    A[1] = A_prime[0]
    ans[1] = A[1]
    res.append(ans[1])
    
    for i in range(2, N+1):
        A_i = A_prime[i-1] ^ ans[i-1]
        A[i] = A_i
        
        max_med = A_i
        window = deque()
        window.append(A_i)
        sorted_window = [A_i]  # 维护一个排序的列表
        med = sorted_window[len(sorted_window)//2]
        current_max = med
        
        for j in range(i-1, 0, -1):
            new_val = A[j]
            # 插入到排序列表中的正确位置
            pos = 0
            while pos < len(sorted_window) and sorted_window[pos] < new_val:
                pos +=1
            sorted_window.insert(pos, new_val)
            
            # 计算中位数
            n = len(sorted_window)
            idx = (n-1)//2
            med = sorted_window[idx]
            if med > current_max:
                current_max = med
            
            # 更新max_med
            if current_max > max_med:
                max_med = current_max
        
        ans[i] = max_med
        res.append(ans[i])
    
    for num in res:
        print(num)
    
if __name__ == "__main__":
    main()
0