結果

問題 No.1786 Maximum Suffix Median (Online)
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:53:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,132 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 115,460 KB
最終ジャッジ日時 2025-03-31 17:54:28
合計ジャッジ時間 4,953 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def main():
    input = sys.stdin.read
    data = list(map(int, input().split()))
    N = data[0]
    A_prime = data[1:N+1]

    ans = []
    A = []
    prev_ans = 0
    K = 200  # Heuristic value
    
    for i in range(N):
        current = A_prime[i] ^ prev_ans if i != 0 else A_prime[i]
        A.append(current)
        max_median = current  # The subarray of length 1
        
        # Consider subarrays of length up to K
        start = max(0, i - K + 1)
        for j in range(start, i):
            # subarray A[j..i]
            m = i - j + 1
            k = (m + 1) // 2
            # We need to get the k-th smallest element
            # To avoid sorting each time, we can maintain a list and use a selection algorithm
            # But since m is small (<= K), sorting is acceptable
            sub = A[j:i+1]
            sub_sorted = sorted(sub)
            median = sub_sorted[k-1]
            if median > max_median:
                max_median = median
        
        ans.append(max_median)
        prev_ans = max_median
    
    for a in ans:
        print(a)

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