QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#570891 | #8790. First Billion | HTensor | RE | 0ms | 0kb | Python3 | 1.8kb | 2024-09-17 18:48:31 | 2024-09-17 18:48:32 |
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