QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742753#3136. The Spectrumvwxyz#TL 16ms11208kbPython31.0kb2024-11-13 17:14:262024-11-13 17:14:34

Judging History

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

  • [2024-11-13 17:14:34]
  • 评测
  • 测评结果:TL
  • 用时:16ms
  • 内存:11208kb
  • [2024-11-13 17:14:26]
  • 提交

answer

from functools import lru_cache
N=int(input())
A=list(map(int,input().split()))
M=1000
cnt=[0]*M
for a in A:
    cnt[a]+=1
L,R=0,max(A)
@lru_cache(maxsize=None)
def solve(X,cnt,l,r):
    if max(cnt)==0:
        retu={X}
    elif l<r:
        retu=set()
        for d in range(M-1,-1,-1):
            if cnt[d]:
                for y in (d,R-d):
                    if l<y<r and max(R-d,d)==d:
                        cnt_=list(cnt)
                        ok=True
                        for x in X:
                            cnt_[abs(x-y)]-=1
                            if cnt_[abs(x-y)]<0:
                                ok=False
                        if ok:
                            retu|=solve(tuple(sorted(list(X)+[y])),tuple(cnt_),y,r)
                            retu|=solve(tuple(sorted(list(X)+[y])),tuple(cnt_),l,y)
                break
    return retu
cnt[R-L]-=1
ans_lst=solve(tuple([L,R]),tuple(cnt),L,R)
ans_lst=list(ans_lst)
le=len(ans_lst)
ans_lst.sort()
print(le)
for i in range(le):
    print(*ans_lst[i])

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 10756kb

input:

4
2 2 2 4 4 6

output:

1
0 2 4 6

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 16ms
memory: 10712kb

input:

5
3 3 6 9 9 12 12 15 18 21

output:

2
0 3 12 15 21
0 6 9 18 21

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 15ms
memory: 10716kb

input:

4
5 6 7 8 9 10

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 14ms
memory: 11208kb

input:

9
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 5 5 6 6 7 7 8 8 8 9 9 10 10 11 11 12 12 12 13 14 15

output:

4
0 1 3 4 5 7 12 13 15
0 1 3 8 9 11 12 13 15
0 2 3 4 6 7 12 14 15
0 2 3 8 10 11 12 14 15

result:

ok 5 lines

Test #5:

score: -100
Time Limit Exceeded

input:

62
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 19 20 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 51 52 55 56 57 58 59 61 62 63 64 65 66 67 68 69 70 71 72 73
0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 21 22 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 ...

result: