結果

問題 No.1946 ロッカーの問題
ユーザー lam6er
提出日時 2025-04-16 00:16:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,079 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 148,612 KB
最終ジャッジ日時 2025-04-16 00:18:16
合計ジャッジ時間 3,673 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+M]))
    
    A_set = set(A)
    A_sorted = A  # already sorted as per input constraints
    
    sum_ = [0] * (N + 2)  # sum_1 to sum_N
    total_skipped = 0
    
    for k in range(1, N + 1):
        s = int(math.isqrt(k))
        is_square = (s * s == k)
        pos = bisect.bisect_left(A_sorted, k)
        in_A = pos < M and A_sorted[pos] == k
        
        # Calculate c_k
        if in_A:
            c_k = 0 if is_square else 1
        else:
            c_k = 1 if is_square else 0
        
        current_sum = sum_[k]
        x_k = (c_k - current_sum) % 2
        total_skipped += x_k
        
        # Update sum for multiples of k
        if x_k == 1:
            multiple = 2 * k
            while multiple <= N:
                sum_[multiple] ^= 1
                multiple += k
    
    print(total_skipped)

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