QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#570891#8790. First BillionHTensorRE 0ms0kbPython31.8kb2024-09-17 18:48:312024-09-17 18:48:32

Judging History

你现在查看的是最新测评结果

  • [2024-09-17 18:48:32]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-17 18:48:31]
  • 提交

answer

import sys
import itertools
from collections import defaultdict

def main():
    import sys
    import threading

    def solve():
        N, *rest = map(int, sys.stdin.read().split())
        A = rest[:N]
        target = 10**9

        # 分桶数量
        B = 36
        buckets = [[] for _ in range(B)]
        for i, num in enumerate(A):
            buckets[i % B].append((num, i+1))  # 存储数值和索引

        # 生成每个桶的所有可能子集和
        subset_sums = []
        for bucket in buckets:
            sums = defaultdict(list)
            sums[0] = []
            for num, idx in bucket:
                current = list(sums.keys())
                for s in current:
                    new_sum = s + num
                    if new_sum <= target:
                        if new_sum not in sums:
                            sums[new_sum] = sums[s] + [idx]
                # 可以选择不添加任何数
            subset_sums.append(sums)

        # 合并桶的子集和
        current_sums = defaultdict(list)
        current_sums[0] = []
        for sums in subset_sums:
            temp = defaultdict(list)
            for s1 in current_sums:
                indices1 = current_sums[s1]
                for s2 in sums:
                    new_sum = s1 + s2
                    if new_sum > target:
                        continue
                    if new_sum not in temp:
                        temp[new_sum] = indices1 + sums[s2]
                        if new_sum == target:
                            print(len(temp[new_sum]), *temp[new_sum])
                            return
            current_sums = temp

        # 如果没有找到
        print(-1)

    threading.Thread(target=solve).start()

if __name__ == "__main__":
    main()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

10
386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997

output:


result: