QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33136#960. Output Limit ExceededWu_RenAC ✓865ms6108kbC++171.5kb2022-05-28 15:17:392022-05-28 15:17:41

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-05-28 15:17:41]
  • Judged
  • Verdict: AC
  • Time: 865ms
  • Memory: 6108kb
Show
  • [2022-05-28 15:17:39]
  • Submitted

answer

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
int head[6010],o=1,S,T,cnt,dep[6010],cur[6010],_k[70],res[7000],t=0;
bool ans[6010];
struct edge{
	int to,link,w;
}e[200010];
void add_edge(int u,int v,int w){
	e[++o]={v,head[u],w},head[u]=o;
	e[++o]={u,head[v],0},head[v]=o;
}
queue<int>q;
bool bfs(){
	for(int i=1;i<=cnt;i++) dep[i]=0,cur[i]=head[i];
	dep[S]=1,q.push(S);
	while(q.size()){
		int u=q.front();q.pop();
		for(int i=head[u],v;i;i=e[i].link) if(!dep[v=e[i].to]&&e[i].w){
			dep[v]=dep[u]+1;
			q.push(v);
		}
	}
	return dep[T];
}
int dfs(int u,int in){
	if(u==T) return in;
	int out=0;
	for(int &i=cur[u],v;i;i=e[i].link) if(dep[v=e[i].to]==dep[u]+1&&e[i].w){
		int res=dfs(v,min(in,e[i].w));
		in-=res,out+=res;
		e[i].w-=res,e[i^1].w+=res;
		if(!in) break;
	}
	if(!out) dep[u]=0;
	return out;
}
int main(){
	scanf("%lld",&n);
	int K=min(3000ll,n/2);
	res[++t]=ans[0]=1,S=2*K+1,cnt=T=2*K+2;
	int mx=0;
	for(int i=1;i<=K;i++){
		add_edge(S,i,1),add_edge(i+K,T,1);
		for(int j=1;j<=i;j++) if((n-j+1)%i==0) add_edge(i,j+K,1);
		for(int j=1;j<=i;j++) if((n-i+1)%j==0) add_edge(j,i+K,1);
		while(bfs()) mx+=dfs(S,2e9);
		res[++t]=ans[i]=i==mx;
	}
	int m=1;
	_k[0]=0;
	for(int j=1;j<60;j++) _k[j]=++m;
	printf("%d\n",m+1);
	for(int j=1;j<60;j++) printf("2 %d %d\n",_k[j-1],_k[j-1]);
	if(2*K==n) t--;
	ll len=max(n-2*K-1,0ll);
	for(int j=0;j<60;j++) if((len>>j)&1) res[++t]=_k[j];
	for(int i=K;i>=0;i--) res[++t]=ans[i];
	printf("%d ",t);
	for(int i=1;i<=t;i++) cout<<res[i]<<" ";puts("");
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3784kb

input:

1

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 2 ones: 0 1

Test #2:

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

input:

0

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 1 ones: 0

Test #3:

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

input:

7

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 6 ones: 0 1 2 5 6 7

Test #4:

score: 0
Accepted
time: 23ms
memory: 3944kb

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: 737ms
memory: 6060kb

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: 791ms
memory: 4656kb

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: 800ms
memory: 4624kb

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: 704ms
memory: 5976kb

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: 657ms
memory: 4652kb

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: 684ms
memory: 4524kb

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: 693ms
memory: 4544kb

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: 748ms
memory: 4656kb

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: 741ms
memory: 4524kb

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: 865ms
memory: 4624kb

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: 732ms
memory: 4520kb

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: 623ms
memory: 6108kb

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: 816ms
memory: 4700kb

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: 805ms
memory: 4612kb

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: 793ms
memory: 4660kb

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: 806ms
memory: 4656kb

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: 777ms
memory: 4520kb

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: 776ms
memory: 4656kb

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: 760ms
memory: 4532kb

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 繁體中文 简体中文

Server Time: 2025-02-08 17:56:18 | OpenSource Project