QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#38337 | #1183. Sum of Palindromes | NaCly_Fish | AC ✓ | 72ms | 19324kb | C++14 | 1.7kb | 2022-07-05 11:07:01 | 2022-07-05 11:07:03 |
Judging History
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!