QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423049#8349. 零和Diu100 ✓106ms12856kbC++142.7kb2024-05-27 20:54:002024-05-27 20:54:02

Judging History

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

  • [2024-05-27 20:54:02]
  • 评测
  • 测评结果：100
  • 用时：106ms
  • 内存：12856kb
查看
  • [2024-05-27 20:54:00]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int k,n,a[40]={0,1,1,1,1,1,2,2,2,5,2,3,3,3,3,3,5,4,4,4,4,5,5};
int f[N],pre[N],len[N];
int rd(int k){return (rand())%k+1;}
void init(){
//	for(int i=1;i<=22;i++)a[i]=rd(5);
	f[0]=1;int s=0;
	for(int i=1;i<=22;i++){
		for(int j=s;j>=0;j--)f[j+a[i]]+=f[j];
		s+=a[i];
	}
	pre[0]=1;
	int dn=(s>>1)+1;
	for(int i=1;i<N;i++){
		len[i]=N;
		for(int j=dn;j<=s;j++){
			if(f[j]>i)continue;
			if(len[i-f[j]]<len[i])len[i]=len[i-f[j]]+1,pre[i]=j;
		}
		if(len[i]>8){
			init();return;
		}
	}
}
signed main(){
	srand(time(0));
	int _;scanf("%d",&_);
	init();
	for(;_--;){
		scanf("%d",&k);
		int n=22;--k;
		while(k)a[++n]=pre[k],k-=f[pre[k]];
		printf("%d\n",n);
		for(int i=1;i<=22;i++)printf("%d ",a[i]);
		for(int i=23;i<=n;i++)printf("%d ",-a[i]);
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 105ms
memory: 12740kb

input:

1000
4
10
9
7
5
9
4
4
10
8
2
10
8
8
4
2
10
4
9
9
8
9
6
9
5
6
9
1
2
5
8
4
4
8
2
2
7
6
8
2
3
1
1
3
1
10
6
3
4
1
6
7
1
5
7
7
3
6
3
3
9
6
9
5
7
5
9
8
3
5
2
4
9
3
10
2
10
10
3
1
9
4
8
9
6
6
6
7
7
7
10
1
2
3
2
6
6
8
1
3
10
8
5
7
8
2
7
9
3
1
9
9
1
10
6
7
9
9
7
9
1
2
7
3
1
5
4
9
2
6
4
9
9
10
4
4
5
9
10
2
2
...

output:

25
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -64 27
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -64 -64 -63 26
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -64 -63 24
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -63 26
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -...

result:

ok Accepted

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 15
Accepted
time: 105ms
memory: 12856kb

input:

1000
42
56
95
81
26
68
42
3
83
6
37
52
5
82
59
10
43
90
44
55
83
8
43
14
94
84
92
61
10
98
46
58
43
49
81
29
36
3
93
38
70
86
54
89
75
28
87
74
56
22
47
89
90
26
76
80
55
90
60
32
58
67
70
94
52
95
78
70
39
40
69
99
18
24
32
33
23
95
19
80
98
59
79
57
69
35
25
72
27
72
57
13
55
37
90
59
53
10
2
84
4...

output:

25
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -63 -61 26
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -63 -62 -61 24
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -62 -60 23
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -60 26
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -63 -63 -62 29
1 1 1 ...

result:

ok Accepted

Subtask #3:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #3:

score: 15
Accepted
time: 106ms
memory: 12644kb

input:

1000
1458
1427
1927
1845
764
1218
986
13
1479
494
1405
1711
88
1701
536
1286
1735
711
63
439
469
1726
739
1496
1055
1775
1946
860
134
742
1296
188
373
1156
230
1366
1123
1601
1015
481
1177
250
723
1265
1254
416
329
489
661
305
1895
1057
1676
676
1972
1031
1721
1483
1046
387
1522
1936
1778
1526
27
11...

output:

28
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -63 -61 -60 -58 -56 26
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -60 -59 -59 -56 26
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -63 -58 -57 -56 29
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -63 -62 -62 -61 -60 -55 28
1 1 1 1 1 2 2 2 5 2 3 3 3...

result:

ok Accepted

Subtask #4:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #4:

score: 15
Accepted
time: 106ms
memory: 12556kb

input:

1000
8882
3890
5276
2293
7017
8729
4107
8330
9804
3437
7125
8266
505
902
10
4246
46
4186
7869
6510
3510
681
8065
2419
1575
2776
2762
5567
3150
5914
4695
6152
2758
5157
1407
5964
8947
8203
7821
3411
3115
8356
8240
3506
1618
1108
4024
5791
2644
3315
3577
9512
5256
3454
7378
9383
4904
6094
8422
7100
71...

output:

28
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -61 -59 -58 -56 -56 -52 27
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -62 -59 -58 -55 -55 29
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -62 -62 -62 -56 -53 28
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -63 -63 -57 -55 26
1 1 1 1 1 2 2...

result:

ok Accepted

Subtask #5:

score: 15
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #5:

score: 15
Accepted
time: 103ms
memory: 12048kb

input:

1000
96341
68443
37369
95002
5050
28444
863
40283
5948
58559
90074
93374
20434
66458
42427
81860
19058
44240
61491
29065
18196
59230
70644
48078
44160
52618
31944
3993
66326
63711
62648
80986
90080
12593
36140
908
97838
9909
62779
18661
92388
86436
83715
49365
10604
17467
65898
31682
64543
37267
202...

output:

25
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -52 -48 -44 29
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -61 -60 -60 -54 -44 29
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -63 -62 -60 -56 -49 -49 27
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -60 -58 -46 -45 27
1 1 1 1 1 2 2 2 5 2 3...

result:

ok Accepted

Subtask #6:

score: 25
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #6:

score: 25
Accepted
time: 102ms
memory: 11828kb

input:

1000
68691
709038
403562
87832
620545
194650
877186
754984
970483
972817
576860
95921
320214
328151
977559
803543
893740
413219
868313
153241
553644
186975
758312
166278
963660
596237
523965
976575
92819
743171
220709
536964
847991
151853
256090
912309
286952
609500
293131
143200
850426
155262
98688...

output:

28
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -61 -60 -59 -59 -54 -44 29
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -59 -51 -38 -38 -38 -33 28
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -63 -47 -38 -34 29
1 1 1 1 1 2 2 2 5 2 3 3 3 3 3 5 4 4 4 4 5 5 -64 -64 -62 -60 -53 -46 -46 28
1 1 1...

result:

ok Accepted
English 繁體中文 简体中文

Server Time: 2024-12-03 04:20:41 | OpenSource Project