QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#19708#1183. Sum of PalindromesJohnAlfnovAC ✓29ms3780kbC++202.7kb2022-02-08 13:29:522022-05-06 06:46:05

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-06 06:46:05]
  • Judged
  • Verdict: AC
  • Time: 29ms
  • Memory: 3780kb
  • [2022-02-08 13:29:52]
  • Submitted

answer

#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<ctype.h>
char s[100005],t[100005];
char A[26][100005];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);
		int i,j,n=strlen(s+1),tot=0;
		int X=1;
		while(s[X]=='0'||X+3<=n){
			if(s[X]=='0'){
				++X;
				continue;
			}
			int flag=(s[X]!='1');
			for(i=X+1;i<=n;++i)if(s[i]!='0'){
				flag=1;
				break;
			}
			if(!flag){
				++tot;
				for(int i=1;i<=n-X;++i)
					A[tot][i]='9';
				++tot;
				A[tot][1]='1';
				X=n+1;
				break;
			}
			int Y=(X+n-1)>>1,Z=n-(Y-X);
			for(i=1;i<=Y-X+1;++i)t[i]=s[i+X-1];
			flag=(t[1]!='1');
			for(int i=2;i<=Y-X+1;++i){
				if(t[i]!='0')flag=1;
			}
			for(i=X;i<Y;++i)s[i]='0';
			s[Y]='0'+flag;
			if(flag){
				int wz=Y-X+1;
				--t[wz];
				while(t[wz]<'0'){
					t[wz]+=10;
					t[wz-1]-=1;
					--wz;
				}
			}
			++tot;
			for(i=1;i<=Y-X+1;++i)
				A[tot][i]=t[i];
			for(i=Y-X+2;i<=Z-X;++i)
				A[tot][i]='0';
			for(i=Z-X+1;i<=n-X+1;++i)
				A[tot][i]=t[n+1-i-X+1];
			for(i=n;i>=Z;--i){
				char dy=t[Y-X+1-i+Z];
				if(s[i]<dy){
					s[i]=10+s[i]-dy+'0';
					--s[i-1];
				}else{
					s[i]=s[i]-dy+'0';
				}
			}
			int xx=Z-1;
			while(xx>0&&s[xx]<'0'){
				s[xx]+=10;
				s[xx-1]-=1;
			}
			X=Y;
		}
		if(X==n-2){
			if(s[n]>=s[X]){
				++tot;
				A[tot][1]=s[X];
				A[tot][2]='0';
				A[tot][3]=s[X];
				s[n]=s[n]-s[X]+'0';
				s[X]='0';
			}else if(s[X]>'1'){
				++tot;
				A[tot][1]=s[X]-1;
				A[tot][2]='9';
				A[tot][3]=s[X]-1;
				s[n]=s[n]+11-s[X]+'0';
				s[X]='0';
			}else{
				++tot;
				A[tot][1]='9';
				A[tot][2]='9';
				s[X]='0';
				++s[n];
			}
		}
		while(s[X]=='0')++X;
		while(s[X]>='0'+10){
			s[X]-=10;
			s[X-1]+=1;
			--X;
		}
		if(X==n-1){
			if(s[X]==s[n]){
				++tot;
				A[tot][1]=s[X];
				A[tot][2]=s[n];
				X=n+1;
			}else if(s[X]<s[n]){
				++tot;
				A[tot][1]=s[X];
				A[tot][2]=s[X];
				s[n]=s[n]-s[X]+'0',s[X]='0';
			}else if(s[X]>'1'){
				++tot;
				A[tot][1]=s[X]-1;
				A[tot][2]=s[X]-1;
				s[n]=s[n]+11-s[X]+'0',s[X]='0';
				if(s[n]=='0'+10){
					s[n]-=10;
					s[X]+=1;
				}
			}
		}
		while(s[X]>='0'+10){
			s[X]-=10;
			s[X-1]+=1;
			--X;
		}
		while(s[X]=='0')++X;
		if(X==n-1){
			if(s[n]=='0'){
				++tot;
				A[tot][1]='9';
				s[X]='0',s[n]='1';
			}else{
				++tot;
				A[tot][1]='1';
				A[tot][2]='1';
				s[n]=s[n]-s[X]-1+'0';
			}
		}
		while(s[X]=='0')++X;
		if(X==n){
			++tot;
			A[tot][1]=s[X];
		}
		printf("%d\n",tot);
		for(i=1;i<=tot;++i){
			printf("%s\n",A[i]+1);
			int B=strlen(A[i]+1);
			for(j=1;j<=B;++j)A[i][j]=0;
		}
		for(i=1;i<=n;++i)s[i]='0';
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3780kb

input:

2
378
2020

output:

3
303
66
9
3
1991
22
7

result:

ok OK!

Test #2:

score: 0
Accepted
time: 29ms
memory: 2112kb

input:

10128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
10...

output:

1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
9
1
1
11
2
11
1
2
11
2
2
11
3
2
11
4
2
11
5
2
11
6
2
11
7
2
11
8
2
11
9
3
11
9
1
1
22
2
22
1
2
22
2
2
22
3
2
22
4
2
22
5
2
22
6
2
22
7
2
22
8
2
22
9
3
22
9
1
1
33
2
33
1
2
33
2
2
33
3
2
33
4
2
33
5
2
33
6
2
33
7
2
33
8
2
33
9
3
33
9
1
1
44
2
44
1
2
44
2
2
44
3
2...

result:

ok OK!