結果

問題 No.1444 !Andd
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:16:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,318 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,760 KB
実行使用メモリ 52,872 KB
最終ジャッジ日時 2025-05-14 13:18:22
合計ジャッジ時間 4,446 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Use fast I/O to read input
input = sys.stdin.readline 

def solve():
    # Read input N
    N = int(input())
    # Read sequence A
    A = list(map(int, input().split()))

    # Initialize the set of possible values for X. Start with X=1 before any operations.
    current_values = {1}

    # List to store the count of distinct values after each step
    results_output = []

    # Iterate through each step from i=1 to N (0-indexed loop from 0 to N-1)
    for i in range(N):
        
        # Calculate the set of possible values for X after the i-th operation.
        # Use a temporary set `next_values_calc` to store the new values.
        next_values_calc = set()
        
        # Get the current element A[i]
        current_Ai = A[i]

        # Optimization: If the current set of values only contains 0, 
        # any operation (multiplication or AND) with any A[i] will result in 0.
        # The set remains {0}.
        # We can check this efficiently. Note: {0} check could be done even earlier,
        # but placing it here simplifies the flow. If current_values is already {0}, 
        # the loop below won't run, and next_values_calc remains empty. We'll fix this after the loop.
        
        # Optimization: If A[i] is 0, then both X * A[i] and X AND A[i] result in 0.
        # The set of possible values after this step will be just {0}.
        if current_Ai == 0:
            next_values_calc = {0}
        # Handle the general case where A[i] > 0 and current_values is not {0}
        else:
            # Iterate through each possible value `x` from the previous step
            for x in current_values:
                # Calculate result of multiplication
                res_mul = x * current_Ai
                next_values_calc.add(res_mul)

                # Calculate result of bitwise AND
                # Python integers handle arbitrary size, so no overflow issues
                # The bitwise AND operation `&` is used.
                res_and = x & current_Ai
                next_values_calc.add(res_and)

        # Update the set of current values for the next iteration
        current_values = next_values_calc
        
        # Get the number of distinct values after the i-th operation
        current_size = len(current_values)
        # Store the size as a string for efficient printing later
        results_output.append(str(current_size))

        # Optimization: If the set of values has become {0},
        # it will remain {0} for all subsequent steps.
        # The size will be 1 for all future steps. We can fill the results and break early.
        # Check if size is 1 and the only element is 0.
        if current_size == 1 and 0 in current_values:
            # Calculate how many steps remain
            remaining_steps = N - (i + 1) # Steps from i+1 to N-1
            # If there are remaining steps, append '1' for each
            if remaining_steps > 0:
                results_output.extend(['1'] * remaining_steps)
            # Exit the loop since future states are determined
            break 

    # Print all the results, each on a new line.
    # Using sys.stdout.write and join is generally faster than multiple print() calls.
    sys.stdout.write("\n".join(results_output) + "\n")

# Call the main solve function
solve()
0