QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167103#1183. Sum of PalindromesDr_rabi3AC ✓161ms19388kbC++201.8kb2023-09-07 03:12:432023-09-07 03:12:44

Judging History

This is the latest submission verdict.

  • [2023-09-07 03:12:44]
  • Judged
  • Verdict: AC
  • Time: 161ms
  • Memory: 19388kb
  • [2023-09-07 03:12:43]
  • Submitted

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!