QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#38337#1183. Sum of PalindromesNaCly_FishAC ✓72ms19324kbC++141.7kb2022-07-05 11:07:012022-07-05 11:07:03

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-07-05 11:07:03]
  • Judged
  • Verdict: AC
  • Time: 72ms
  • Memory: 19324kb
  • [2022-07-05 11:07:01]
  • Submitted

answer

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 200006
#define ll long long
#define p 998244353
using namespace std;

inline bool cmp(const int *f,const int *g,int n){ // f <= g
	for(int i=n-1;i>=0;--i){
		if(f[i]==g[i]) continue;
		return f[i]<g[i];
	}
	return true;
}

int a[N],b[27][N],d[27];
char str[N];
int cnt,len,blen;

int main(){
	int T,n;
	scanf("%d",&T);
	while(T--){
		cnt = n = 0;
		scanf("%s",str);
		n = strlen(str);
		for(int i=0;i<n;++i) a[i] = str[n-i-1]-'0';
		while(n>1){
			if(n==2&&a[1]==1){
				if(a[0]==0) d[cnt] = 1,b[cnt][0] = 9,a[0]++;
				else d[cnt] = 2,b[cnt][0] = b[cnt][1] = 1,a[0]--;
				a[1] = 0;
				++cnt;
				break;
			}
			blen = n;
			len = (n&1)?(n>>1)+1:n>>1;
			for(int i=0;i<len;++i) b[cnt][i] = b[cnt][n-i-1] = a[n-i-1];
			
			if(!cmp(b[cnt],a,n)){
				int pt = len;
				while(a[n-pt]==0) --pt;
				if(pt>1) b[cnt][pt-1] = b[cnt][n-pt] = a[n-pt]-1;
				else{
					blen = n-1;
					for(int i=0;i<blen;++i) b[cnt][i] = 9;
					b[cnt][n-1] = 0;
				}
			}	
			//for(int i=n-1;i>=0;--i) putchar(a[i]+'0');
			//putchar('\n');
			//for(int i=blen-1;i>=0;--i) putchar(b[cnt][i]+'0');
			//putchar('\n');
			for(int i=blen-1;i>=0;--i) a[i] -= b[cnt][i];
			for(int i=0;i<n;++i){
				if(a[i]>=0) continue;
				a[i+1]--;
				a[i] += 10;
			}
			//putchar('\n');
			//for(int i=n-1;i>=0;--i) putchar(a[i]+'0');
			//puts("\n");
			while(a[n-1]==0&&n>1) n--;
			d[cnt++] = blen;
		}
		//continue;
		printf("%d\n",cnt+(a[0]>0));
		for(int i=0;i<cnt;++i){
			for(int j=d[i]-1;j>=0;--j) putchar(b[i][j]+'0');
			putchar('\n');
		}
		if(a[0]>0) printf("%d\n",a[0]);
	}
	return 0;
}

詳細信息

Test #1:

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

input:

2
378
2020

output:

2
373
5
3
2002
11
7

result:

ok OK!

Test #2:

score: 0
Accepted
time: 72ms
memory: 19324kb

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
9
11
3
9
11
1
1
22
2
22
1
2
22
2
2
22
3
2
22
4
2
22
5
2
22
6
2
22
7
4
9
9
11
1
2
9
22
3
9
22
1
1
33
2
33
1
2
33
2
2
33
3
2
33
4
2
33
5
2
33
6
3
9
9
22
4
9
9
22
1
2
9
33
3
9
33
1
1
44
2
44
1
2
44
...

result:

ok OK!