QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54374#960. Output Limit ExceededtricyzhkxAC ✓4ms3800kbC++141.3kb2022-10-08 08:57:122022-10-08 08:57:15

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-08 08:57:15]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 3800kb
Show
  • [2022-10-08 08:57:12]
  • Submitted

answer

# include <bits/stdc++.h>
using namespace std;
const int B=300;
typedef long long ll;
bool ans[400],vis[400];
int mch[800];
ll n;
vector<int> G[400];
bool dfs(int u)
{
	if(vis[u]) return false;
	vis[u]=1;
	for(int v:G[u])
	{
		int w=mch[v];
		mch[u]=v;mch[v]=u;mch[w]=0;
		if(!w || dfs(w)) return true;
		mch[u]=0;mch[v]=w;mch[w]=v;
	}
	return false;
}
void solve(int K)
{
	for(int i=1;i<=K;i++)
	{
		G[i].push_back(K+n-n/i*i+1);
		assert(K+n-n/i*i+1<=2*K);
		for(int j=1;j<i;j++)
			if((n-i+1)%j==0) G[j].push_back(K+i);
		memset(vis,0,sizeof(vis));
		for(int j=1;j<=i;j++)
			if(!mch[j] && dfs(j))
				memset(vis,0,sizeof(vis));
		ans[i]=1;
		for(int j=1;j<=i;j++) ans[i]&=(mch[j]>0);
	}
}
int main()
{
	cin>>n;
	ans[0]=1;
	if(n<=2*B+100)
	{
		solve(n/2);
		printf("2\n%lld ",n+1);
		for(int i=0;i<=n;i++)
			if(i<=n/2) printf("%d%c",ans[i]," \n"[i==n]);
			else printf("%d%c",ans[n-i]," \n"[i==n]);
		return 0;
	}
	solve(B);
	puts("61\n2 0 0");
	for(int i=3;i<=60;i++) printf("2 %d %d\n",i-1,i-1);
	vector<int> vec;
	for(int i=0;i<=B;i++) vec.push_back(ans[i]);
	ll len=n-2*B-1;
	for(int i=0;len;i++,len>>=1)
		if(len&1) vec.push_back(i?i+1:i);
	for(int i=B;i>=0;i--) vec.push_back(ans[i]);
	cout<<vec.size();
	for(int i:vec) printf(" %d",i);
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3560kb

input:

1

output:

2
2 1 1

result:

ok OK 2 ones: 0 1

Test #2:

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

input:

0

output:

2
1 1

result:

ok OK 1 ones: 0

Test #3:

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

input:

7

output:

2
8 1 1 1 0 0 1 1 1

result:

ok OK 6 ones: 0 1 2 5 6 7

Test #4:

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

input:

1000

output:

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

result:

ok OK 18 ones: 0 1 2 3 4 5 6 7 9 991 993 994 995 996 997 998 999 1000

Test #5:

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

input:

1000000000000000000

output:

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

result:

ok OK 14 ones: 0 1 2 3 4 5 6 999999999999999994 999999999999999995 999999999999999996 999999999999999997 999999999999999998 999999999999999999 1000000000000000000

Test #6:

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

input:

987654321987654321

output:

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

result:

ok OK 10 ones: 0 1 2 3 4 987654321987654317 987654321987654318 987654321987654319 987654321987654320 987654321987654321

Test #7:

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

input:

268571729873867564

output:

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

result:

ok OK 8 ones: 0 1 2 3 268571729873867561 268571729873867562 268571729873867563 268571729873867564

Test #8:

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

input:

7900225

output:

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

result:

ok OK 18 ones: 0 1 2 5 6 19 20 25 26 7900199 7900200 7900205 7900206 7900219 7900220 7900223 7900224 7900225

Test #9:

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

input:

1690950

output:

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

result:

ok OK 22 ones: 0 1 2 3 4 5 6 7 23 24 25 1690925 1690926 1690927 1690943 1690944 1690945 1690946 1690947 1690948 1690949 1690950

Test #10:

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

input:

3299430

output:

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

result:

ok OK 20 ones: 0 1 2 3 4 5 6 7 8 27 3299403 3299422 3299423 3299424 3299425 3299426 3299427 3299428 3299429 3299430

Test #11:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

3755426

output:

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

result:

ok OK 12 ones: 0 1 2 3 7 27 3755399 3755419 3755423 3755424 3755425 3755426

Test #12:

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

input:

7900224

output:

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

result:

ok OK 26 ones: 0 1 2 3 4 5 19 20 21 22 23 24 25 7900199 7900200 7900201 7900202 7900203 7900204 7900205 7900219 7900220 7900221 7900222 7900223 7900224

Test #13:

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

input:

582120

output:

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

result:

ok OK 34 ones: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 23 24 25 582095 582096 582097 582107 582108 582109 582110 582111 582112 582113 582114 582115 582116 582117 582118 582119 582120

Test #14:

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

input:

186145

output:

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

result:

ok OK 12 ones: 0 1 2 5 6 26 186119 186139 186140 186143 186144 186145

Test #15:

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

input:

5392796

output:

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

result:

ok OK 20 ones: 0 1 2 3 5 6 7 8 9 25 5392771 5392787 5392788 5392789 5392790 5392791 5392793 5392794 5392795 5392796

Test #16:

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

input:

1690947

output:

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

result:

ok OK 14 ones: 0 1 2 3 4 5 25 1690922 1690942 1690943 1690944 1690945 1690946 1690947

Test #17:

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

input:

763452298

output:

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

result:

ok OK 22 ones: 0 1 2 3 4 5 6 7 8 9 29 763452269 763452289 763452290 763452291 763452292 763452293 763452294 763452295 763452296 763452297 763452298

Test #18:

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

input:

701578836

output:

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

result:

ok OK 26 ones: 0 1 2 3 4 5 6 7 8 9 10 11 29 701578807 701578825 701578826 701578827 701578828 701578829 701578830 701578831 701578832 701578833 701578834 701578835 701578836

Test #19:

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

input:

308897850

output:

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

result:

ok OK 18 ones: 0 1 2 3 4 5 6 7 27 308897823 308897843 308897844 308897845 308897846 308897847 308897848 308897849 308897850

Test #20:

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

input:

377596828

output:

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

result:

ok OK 18 ones: 0 1 2 3 4 5 6 23 27 377596801 377596805 377596822 377596823 377596824 377596825 377596826 377596827 377596828

Test #21:

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

input:

524422078

output:

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

result:

ok OK 42 ones: 0 1 2 3 4 5 6 7 8 9 10 11 16 17 18 19 20 21 23 27 29 524422049 524422051 524422055 524422057 524422058 524422059 524422060 524422061 524422062 524422067 524422068 524422069 524422070 524422071 524422072 524422073 524422074 524422075 524422076 524422077 524422078

Test #22:

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

input:

906130371972379050

output:

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

result:

ok OK 20 ones: 0 1 2 3 4 5 6 7 8 31 906130371972379019 906130371972379042 906130371972379043 906130371972379044 906130371972379045 906130371972379046 906130371972379047 906130371972379048 906130371972379049 906130371972379050

Test #23:

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

input:

9469980

output:

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

result:

ok OK 18 ones: 0 1 2 3 4 5 6 7 31 9469949 9469973 9469974 9469975 9469976 9469977 9469978 9469979 9469980
English 繁體中文 简体中文

服务器时间: 2025-02-08 18:14:13 | 开源项目