QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#167103 | #1183. Sum of Palindromes | Dr_rabi3 | AC ✓ | 161ms | 19388kb | C++20 | 1.8kb | 2023-09-07 03:12:43 | 2023-09-07 03:12:44 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
constexpr int mod = 1e9 + 7, oo = 0x3f3f3f3f, N = 200006;
using namespace std;
inline bool cmp(const int* f, const int* g, int n) {
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];
int cnt, len, blen;
void doWork() {
cnt = 0;
string str;
cin >> str;
int n = str.size();
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 = 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;
}
while (a[n - 1] == 0 && n > 1) n--;
d[cnt++] = blen;
}
cout << cnt + (a[0] > 0) << '\n';
for (int i = 0;i < cnt;++i) {
for (int j = d[i] - 1;j >= 0;--j) cout << b[i][j];
cout << '\n';
}
if (a[0] > 0) cout << a[0] << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int t = 1;
cin >> t;
while (t--) {
doWork();
// cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5448kb
input:
2 378 2020
output:
2 373 5 3 2002 11 7
result:
ok OK!
Test #2:
score: 0
Accepted
time: 161ms
memory: 19388kb
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!