結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
ユーザー qwewe
提出日時 2025-04-24 12:32:09
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,467 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 537,412 KB
最終ジャッジ日時 2025-04-24 12:33:29
合計ジャッジ時間 5,639 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    n = int(sys.stdin.readline())
    c = list(map(int, sys.stdin.readline().split()))
    digits = []
    for i in range(9):
        digits.extend([i+1] * c[i])
    even_digits = [d for d in digits if d % 2 == 0]
    if not even_digits:
        print(0)
        return

    max_k = 0

    # We need to check from high k down to 1
    for k in range(40, 0, -1):
        mod = 1 << k
        # Precompute 10^p mod mod for each position p (0-based from left)
        # positions are 0 to n-1, exponent is 10^{n-1 - p}
        power_of_10 = [pow(10, (n-1 - p), mod) for p in range(n)]

        # We need to track the count of each digit used and the remainder
        # We'll use a memoization approach with the current remainder and counts
        # But since counts can be up to 14, we need a way to represent it efficiently
        # Let's use a tuple of counts for each digit (from 1 to 9)
        counts = c.copy()
        from collections import defaultdict

        # Memoization cache: (position, remainder, counts_tuple) -> boolean
        # But since counts can be large, we need a better way
        # Alternative approach: use a bitmask for counts (not feasible for 9 digits)
        # Instead, use a dictionary to memoize the state

        # We'll use a recursive approach with memoization
        memo = {}

        def backtrack(pos, rem, cnts):
            key = (pos, rem, tuple(cnts))
            if key in memo:
                return memo[key]
            if pos == n:
                return rem == 0
            # Try all possible digits
            for d in range(1, 10):
                if cnts[d-1] == 0:
                    continue
                # Check if this digit can be placed at the current position
                # For the last position, it must be even
                if pos == n-1 and d % 2 != 0:
                    continue
                new_cnts = cnts.copy()
                new_cnts[d-1] -= 1
                contribution = (d * power_of_10[pos]) % mod
                new_rem = (rem + contribution) % mod
                if backtrack(pos + 1, new_rem, new_cnts):
                    memo[key] = True
                    return True
            memo[key] = False
            return False

        # Check if there's a valid arrangement
        if backtrack(0, 0, c.copy()):
            print(k)
            return

    print(0)

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