QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#23961#2809. Presentnantf100 ✓393ms7868kbC++203.0kb2022-03-23 18:27:042022-04-30 04:36:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 04:36:26]
  • 评测
  • 测评结果：100
  • 用时：393ms
  • 内存：7868kb
查看
  • [2022-03-23 18:27:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1 << 19, biao[] = {0,2,4,7,13,22,38,67,121,208,346,663,1067,2084,3650,5621,10187,20228,33960,67673,106919,167302,316644,632549,988585,1672754,3243116,5502723,9032101,18060326,26876518,53747047,97409341,162001788,320354230,488138971,761529731,1523024388};
int T, k[5], _[38][38], mzk[N], sum[N];
vector<int> ans[5];
bitset<N> oke, okl;
int main(){
	ios::sync_with_stdio(false);
	cin >> T;
	for(int i = 0;i < T;++ i) cin >> k[i];
	for(int i = 1;i < 38;++ i)
		for(int j = 1;j < 38;++ j)
			_[i-1][j-1] = __gcd(i, j);
	for(int m = 1;m < 38;++ m){
		bool flg = false;
		for(int i = 0;i < T;++ i) flg |= k[i] >= biao[m-1] && k[i] < biao[m];
		if(!flg) continue;
		int md = m>>1, le = 1<<md, lo = 1<<m-md;
		memset(mzk, 0, lo<<2);
		oke.reset(); okl.reset();
		for(int S = 0;S < le;++ S){
			bool flg = true;
			for(int i = 0;i < md && flg;++ i) if(S >> i & 1)
				for(int j = i+1;j < md && flg;++ j)
					if((S >> j & 1) && !(S >> _[i][j]-1 & 1))
						flg = false;
			if(flg) oke.set(S);
		}
		for(int S = 0;S < lo;++ S){
			bool flg = true;
			for(int i = 0;i < m-md && flg;++ i) if(S >> i & 1)
				for(int j = i+1;j < m-md && flg;++ j)
					if((S >> j & 1) && !(S >> (_[i<<1][j<<1]>>1) & 1))
						flg = false;
			if(!flg) continue;
			okl.set(S);
			for(int j = 0;j < md;++ j){
				flg = true;
				for(int i = 0;i < m-md && flg;++ i)
					if((S >> i & 1) && !(S >> (_[i<<1][j]>>1) & 1))
						flg = false;
				if(flg) mzk[S] |= 1 << j;
			}
		}
		auto calc = [&](int od0, int od1, int ev0, int ev1){
			vector<int> tmp; tmp.clear();
			for(int i = 0;i < md;++ i)
				if(ev1 >> i & 1) tmp.push_back(i);
			int L = tmp.size(), lim = 1<<L;
			for(int i = 0;i < lim;++ i){
				int S = 0;
				for(int j = 0;j < L;++ j)
					if(i >> j & 1) S |= 1 << tmp[j];
				sum[i] = oke[ev0 | S];
			}
			for(int md = 1;md < lim;md <<= 1)
				for(int i = 0;i < lim;i += md<<1)
					for(int j = 0;j < md;++ j)
						sum[i | j | md] += sum[i | j];
			LL res = 0;
			for(int i =	od1;;i = i-1 & od1){
				if(okl[od0 | i] && (mzk[od0 | i] & ev0) == ev0){
					int hah = 0;
					for(int j = 0;j < L;++ j)
						if(mzk[od0 | i] >> tmp[j] & 1) hah |= 1 << j;
					res += sum[hah];
				}
				if(!i) break;
			}
			return res;
		};
		for(int i = 0;i < T;++ i) if(k[i] >= biao[m-1] && k[i] < biao[m]){
			int od0 = 0, od1 = lo-1, ev0 = 0, ev1 = le-1;
			k[i] -= biao[m-1];
			(m & 1 ? od0 : ev0) |= 1 << (m-1>>1);
			(m & 1 ? od1 : ev1) &= ~(1 << (m-1>>1));
			ans[i].push_back(m);
			for(int j = m-1;j;-- j){
				(j & 1 ? od1 : ev1) &= ~(1 << (j-1>>1));
				int res = calc(od0, od1, ev0, ev1);
				if(k[i] >= res){
					k[i] -= res;
					(j & 1 ? od0 : ev0) |= 1 << (j-1>>1);
					ans[i].push_back(j);
				}
			}
			reverse(ans[i].begin(), ans[i].end());
			k[i] = 0;
		}
	}
	for(int i = 0;i < T;++ i){
		cout << ans[i].size();
		for(int u : ans[i]) cout << ' ' << u;
		cout << '\n';
	}
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 4ms
memory: 7716kb

input:

5
62
37
88
57
72

output:

5 1 2 5 6 7
6 1 2 3 4 5 6
4 1 2 6 8
4 1 3 6 7
4 1 2 3 8

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5812kb

input:

5
88
77
21
87
24

output:

4 1 2 6 8
4 1 3 4 8
5 1 2 3 4 5
3 2 6 8
2 2 6

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 5736kb

input:

5
59
5
72
76
95

output:

5 1 2 4 6 7
2 1 3
4 1 2 3 8
4 1 2 4 8
6 1 2 4 5 6 8

result:

ok 5 lines

Test #4:

score: 0
Accepted
time: 3ms
memory: 5848kb

input:

5
3
58
50
91
38

output:

2 1 2
5 1 2 3 6 7
5 1 2 3 5 7
5 1 2 4 6 8
1 7

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 5808kb

input:

5
6
38
78
60
52

output:

3 1 2 3
1 7
5 1 2 3 4 8
6 1 2 3 4 6 7
5 1 2 4 5 7

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 3ms
memory: 5808kb

input:

5
53
2
54
17
77

output:

5 1 3 4 5 7
1 2
6 1 2 3 4 5 7
4 1 2 3 5
4 1 3 4 8

result:

ok 5 lines

Subtask #2:

score: 21
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 21
Accepted
time: 2ms
memory: 5752kb

input:

5
967473
149056
95798
903699
54343

output:

14 1 2 3 6 7 9 14 15 17 18 21 22 23 24
7 1 3 4 8 17 20 21
9 1 2 5 7 11 15 17 19 20
17 1 2 3 4 6 7 8 10 12 13 14 18 19 20 21 23 24
7 1 2 4 8 11 18 19

result:

ok 5 lines

Test #8:

score: 0
Accepted
time: 2ms
memory: 5756kb

input:

5
824612
692511
834141
820975
111302

output:

14 1 2 3 4 5 6 7 9 10 11 12 18 23 24
10 1 2 3 5 6 7 10 13 21 24
11 1 3 7 8 9 11 13 15 19 23 24
11 1 3 4 5 8 9 12 15 17 23 24
10 1 2 3 4 6 11 12 13 16 21

result:

ok 5 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 5756kb

input:

5
115600
813100
742542
206782
714068

output:

13 1 2 3 5 6 7 9 10 11 13 15 17 21
9 1 2 3 4 11 12 14 23 24
12 1 2 3 5 6 11 12 14 17 18 22 24
11 1 2 3 5 7 9 11 12 17 19 22
14 1 2 3 4 5 6 9 10 13 17 18 19 21 24

result:

ok 5 lines

Test #10:

score: 0
Accepted
time: 4ms
memory: 5900kb

input:

5
271953
490598
560137
729339
980828

output:

14 1 2 3 4 6 7 8 9 11 13 16 17 21 22
12 1 2 3 4 8 11 12 13 14 16 22 23
12 1 2 4 6 7 10 16 17 18 20 22 23
12 1 2 3 5 7 8 9 10 13 14 22 24
17 1 2 3 4 5 6 7 10 11 12 15 17 20 21 22 23 24

result:

ok 5 lines

Test #11:

score: 0
Accepted
time: 7ms
memory: 5844kb

input:

5
78005
94222
345802
240639
797525

output:

14 1 2 3 4 6 7 9 10 11 12 13 16 17 20
12 1 2 3 4 5 6 7 11 13 17 19 20
12 1 2 3 7 8 9 11 13 14 17 18 23
13 1 2 3 4 5 6 7 10 13 16 18 20 22
13 1 2 3 6 7 8 9 14 18 19 21 22 24

result:

ok 5 lines

Test #12:

score: 0
Accepted
time: 7ms
memory: 5844kb

input:

5
213815
388934
704608
638223
965441

output:

15 1 2 3 4 5 6 9 10 11 13 15 16 17 19 22
11 1 2 3 4 7 10 13 14 16 20 23
14 1 2 3 4 5 6 8 9 10 11 13 19 21 24
8 1 2 4 8 11 14 16 24
17 1 2 3 4 6 7 8 10 11 12 13 14 18 21 22 23 24

result:

ok 5 lines

Subtask #3:

score: 41
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #13:

score: 41
Accepted
time: 193ms
memory: 6320kb

input:

5
264009813
338082986
193952046
78609665
69397288

output:

21 1 2 3 4 5 6 7 8 9 10 12 15 17 18 19 21 24 25 29 33 34
21 1 2 3 4 5 6 7 8 9 10 12 13 14 15 17 23 24 26 28 31 35
20 1 2 3 4 5 7 10 11 13 14 15 16 17 20 21 22 23 28 31 34
17 1 2 3 4 7 8 9 14 16 17 19 20 21 24 27 31 32
18 1 2 3 4 5 6 7 8 10 13 15 17 18 19 24 26 30 32

result:

ok 5 lines

Test #14:

score: 0
Accepted
time: 180ms
memory: 6156kb

input:

5
150219445
322427094
31308257
148721382
412214364

output:

16 1 2 3 4 9 11 13 14 17 18 25 26 27 31 32 33
16 1 2 3 4 5 7 9 10 11 12 17 21 23 24 27 35
15 1 2 3 5 8 9 11 13 15 16 17 18 26 27 31
19 1 2 3 5 8 9 10 11 13 16 17 18 21 22 23 26 31 32 33
17 1 2 3 4 5 7 9 13 18 20 21 22 26 27 29 34 35

result:

ok 5 lines

Test #15:

score: 0
Accepted
time: 232ms
memory: 6924kb

input:

5
151756875
427011464
58969849
244330943
310625967

output:

21 1 2 3 4 5 6 7 8 9 10 11 18 19 20 23 24 27 28 31 32 33
22 1 2 3 4 5 6 7 8 9 16 17 18 19 20 22 23 26 28 29 31 34 35
15 1 2 4 5 7 8 10 14 16 19 22 24 25 28 32
19 1 2 3 4 5 6 8 10 15 16 17 18 23 24 25 29 31 32 34
25 1 2 3 4 5 6 7 10 11 12 13 14 15 17 20 21 22 23 26 27 28 31 32 33 34

result:

ok 5 lines

Test #16:

score: 0
Accepted
time: 324ms
memory: 6748kb

input:

5
179476159
129836662
494167066
336058841
348325607

output:

22 1 2 3 4 5 6 7 8 12 13 15 16 19 21 23 24 25 26 27 28 29 34
22 1 2 3 4 5 6 8 9 10 11 13 14 17 18 20 22 25 27 28 30 31 33
17 1 2 3 4 5 6 7 9 10 14 16 18 19 22 25 29 36
22 1 2 3 4 5 7 8 9 10 11 12 13 14 15 19 20 23 24 25 26 31 35
22 1 2 3 4 5 6 7 10 11 15 19 22 23 24 25 26 27 28 29 30 31 35

result:

ok 5 lines

Test #17:

score: 0
Accepted
time: 152ms
memory: 6108kb

input:

5
337931259
398093956
349469813
381304523
455533754

output:

15 1 2 3 5 6 7 9 13 15 21 22 26 28 31 35
17 1 2 3 4 5 7 9 11 15 17 19 21 26 31 32 33 35
18 1 2 3 4 5 7 8 10 11 12 14 15 16 21 25 26 32 35
17 1 2 3 4 5 10 11 13 15 17 20 22 24 26 31 33 35
22 1 2 3 4 5 6 7 8 9 10 13 14 16 18 19 20 21 23 26 33 34 35

result:

ok 5 lines

Test #18:

score: 0
Accepted
time: 182ms
memory: 6000kb

input:

5
5456876
29594798
37782325
167839691
354330184

output:

17 1 2 3 4 5 6 9 12 13 17 20 21 23 24 25 26 27
12 1 2 3 4 5 14 16 18 22 25 26 31
16 1 2 4 5 6 7 10 11 16 17 18 19 22 26 29 31
18 1 2 3 4 5 6 8 9 10 13 14 15 17 20 23 24 28 34
19 1 2 3 4 5 6 8 9 10 16 17 20 23 24 26 27 29 32 35

result:

ok 5 lines

Subtask #4:

score: 14
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #19:

score: 14
Accepted
time: 200ms
memory: 6520kb

input:

5
518437301
666694742
559265585
512923635
621833328

output:

20 1 2 3 4 5 7 8 9 10 12 13 15 17 19 21 22 23 24 32 36
24 1 2 3 4 5 6 7 8 11 12 13 15 16 19 21 22 25 29 30 31 32 33 34 36
25 1 2 3 4 6 7 8 9 10 11 12 13 14 16 19 20 22 23 24 27 28 29 31 33 36
15 1 2 4 5 7 9 11 14 18 20 27 28 29 31 36
21 1 2 3 4 5 6 8 9 11 12 16 19 20 21 22 25 26 31 32 34 36

result:

ok 5 lines

Test #20:

score: 0
Accepted
time: 372ms
memory: 7148kb

input:

5
633963943
615542568
828135456
568557686
770592955

output:

17 1 2 3 4 7 8 9 11 12 13 14 24 25 26 33 34 36
16 1 2 3 4 6 7 10 13 17 20 26 28 29 32 34 36
18 1 2 4 6 7 11 13 14 16 17 19 20 23 26 28 29 32 37
18 1 2 3 4 5 6 7 11 12 16 17 21 22 26 30 32 33 36
11 1 2 3 4 5 9 10 13 19 29 37

result:

ok 5 lines

Test #21:

score: 0
Accepted
time: 393ms
memory: 7688kb

input:

5
872589670
817203941
677799344
886039387
913475137

output:

20 1 2 3 4 5 6 8 11 12 15 16 17 19 23 25 26 27 30 33 37
19 1 2 3 4 5 6 7 8 10 12 13 15 16 18 22 24 26 32 37
23 1 2 3 4 5 6 7 9 10 12 13 14 16 19 21 22 23 25 26 28 31 35 36
20 1 2 3 4 5 6 8 10 11 17 19 22 23 24 26 27 29 31 33 37
27 1 2 3 4 5 6 7 8 10 11 12 13 14 16 19 20 21 22 23 24 25 27 28 31 32 33...

result:

ok 5 lines

Test #22:

score: 0
Accepted
time: 381ms
memory: 6736kb

input:

5
670654397
910193787
921254051
975272734
607399529

output:

18 1 2 3 5 6 7 10 11 12 13 14 18 19 21 23 29 35 36
20 1 2 3 4 5 6 7 9 10 12 13 19 20 21 23 26 31 32 33 37
27 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 23 29 30 31 32 33 37
17 1 2 3 5 6 9 14 22 23 25 26 28 29 30 31 34 37
18 1 2 4 5 6 7 10 11 16 22 23 25 28 29 30 31 34 36

result:

ok 5 lines

Test #23:

score: 0
Accepted
time: 381ms
memory: 7408kb

input:

5
628012728
924251460
522922329
904744468
644444189

output:

20 1 2 3 4 6 8 12 14 16 17 19 20 22 26 28 29 31 32 34 36
18 1 2 4 6 7 8 10 12 14 16 17 18 19 20 22 24 34 37
19 1 2 3 4 6 7 8 9 10 12 14 17 18 22 23 24 29 32 36
15 1 2 3 4 6 11 12 17 21 22 26 30 32 33 37
22 1 2 3 4 5 6 8 10 11 12 14 15 16 18 19 20 25 28 31 33 34 36

result:

ok 5 lines

Test #24:

score: 0
Accepted
time: 313ms
memory: 6908kb

input:

5
980123780
914372233
788153300
820127076
873721786

output:

19 1 2 3 5 7 10 11 13 14 16 17 21 23 25 26 27 32 34 37
24 1 2 3 4 5 6 7 8 10 11 15 17 18 19 20 21 22 23 24 29 31 32 33 37
20 1 2 3 4 6 9 11 12 13 14 15 17 19 23 26 27 28 29 30 37
11 1 4 5 8 11 16 23 24 28 32 37
21 1 2 3 4 5 6 7 9 10 12 13 14 15 21 25 26 27 28 30 33 37

result:

ok 5 lines

Subtask #5:

score: 16
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #25:

score: 16
Accepted
time: 307ms
memory: 7868kb

input:

5
1358094333
1154803687
1277000267
1417906383
1326768836

output:

18 1 2 3 4 7 8 13 14 16 17 19 20 23 28 31 34 36 37
20 1 2 3 4 5 8 10 11 13 16 17 20 23 25 26 29 32 33 35 37
26 1 2 3 4 5 6 7 8 9 10 11 12 16 17 19 21 22 23 24 25 26 28 30 31 36 37
22 1 2 3 4 5 6 7 8 10 13 15 20 21 23 25 28 29 32 33 34 36 37
17 1 2 3 4 5 9 15 18 20 23 26 27 28 32 33 36 37

result:

ok 5 lines

Test #26:

score: 0
Accepted
time: 315ms
memory: 7008kb

input:

5
1100135829
1287342975
1408078880
1246372296
1263782767

output:

21 1 2 3 4 5 6 7 11 12 13 14 15 16 21 23 25 27 28 31 35 37
22 1 2 3 4 5 6 7 9 10 11 14 18 19 20 21 23 26 28 29 32 36 37
21 1 2 3 4 5 8 10 11 13 15 16 18 21 25 26 29 31 33 34 36 37
24 1 2 3 4 5 6 7 10 12 14 15 16 18 19 23 25 28 29 31 32 33 34 35 37
21 1 2 3 4 5 6 7 8 9 11 12 13 15 16 18 24 28 29 30 3...

result:

ok 5 lines

Test #27:

score: 0
Accepted
time: 317ms
memory: 7804kb

input:

5
1306529540
1338402393
1435825745
1298031139
1263046790

output:

9 1 3 4 13 19 28 33 36 37
22 1 2 3 4 5 6 7 9 10 11 13 14 19 20 21 27 30 31 32 33 36 37
24 1 2 3 4 5 6 7 8 9 10 12 13 14 16 19 24 25 26 27 28 30 35 36 37
22 1 2 3 4 5 6 7 9 11 12 13 14 16 22 23 25 26 29 31 32 36 37
21 1 2 4 5 6 7 8 10 11 12 14 16 19 20 22 24 26 29 30 36 37

result:

ok 5 lines

Test #28:

score: 0
Accepted
time: 308ms
memory: 7400kb

input:

5
1299841326
1050490081
1319190964
1496700273
1351264279

output:

19 1 2 3 4 6 8 9 13 15 18 19 23 26 28 29 31 32 36 37
22 1 2 3 4 5 6 7 9 10 12 14 17 21 23 26 27 28 30 31 33 34 37
20 1 3 4 5 7 8 9 12 16 17 19 20 23 24 27 29 31 33 36 37
27 1 2 3 4 5 6 7 8 9 10 12 13 15 16 17 18 20 21 22 25 27 30 32 34 35 36 37
24 1 2 3 4 5 6 7 8 10 12 13 14 16 17 18 20 21 22 23 26 ...

result:

ok 5 lines

Test #29:

score: 0
Accepted
time: 327ms
memory: 7108kb

input:

5
1126333587
1363542178
1219832547
1117001699
1052017949

output:

26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 17 18 19 22 23 25 26 29 31 32 35 37
18 1 2 4 5 11 13 14 16 17 19 22 25 28 29 31 34 36 37
23 1 2 3 4 5 6 7 8 9 11 14 16 17 18 19 22 23 25 29 33 34 35 37
21 1 2 3 4 5 6 7 8 9 11 15 16 19 20 23 27 28 29 32 35 37
20 1 2 3 4 5 8 9 10 11 13 21 23 25 27 29 30 31 33 34 37

result:

ok 5 lines

Test #30:

score: 0
Accepted
time: 310ms
memory: 6744kb

input:

5
1419871457
1342818229
1195637683
1225498668
1123546639

output:

22 1 2 3 4 5 6 9 11 13 14 15 16 19 23 27 28 30 32 33 34 36 37
15 1 2 3 4 5 6 8 9 13 16 26 27 34 36 37
24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 18 19 20 22 24 27 32 34 35 37
23 1 2 3 4 5 7 10 13 14 15 16 20 23 25 26 27 28 29 30 33 34 35 37
23 1 2 3 4 5 6 7 8 10 11 13 15 16 17 21 24 25 26 27 31 32 35 37

result:

ok 5 lines
English 繁體中文 简体中文

Server Time: 2024-12-02 01:23:06 | OpenSource Project