QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56706 | #3889. Balanced Breakdown | Sa3tElSefr# | AC ✓ | 2ms | 3732kb | C++20 | 2.7kb | 2022-10-21 03:22:07 | 2022-10-21 03:22:07 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define ll long long
#define ld double
using namespace std;
const int N = 1e3 + 5, mod = 998244353;
const ll inf = 1e18;
ll pw[50];
vector<ll> ans;
string getString(ll n) {
string ret = "";
while(n > 0) {
ret.push_back((char) (n % 10) + '0');
n /= 10;
}
reverse(ret.begin(), ret.end());
return ret;
}
void solvePowerOf10(ll n) {
auto cur = getString(n);
if(cur[0] == '1') {
ans.push_back(1);
ans.push_back(n - 1);
}
else{
int digit = 10 - (cur[0] - '0') + 1;
// cout << n << ' ' << digit << ' ' << n - digit << '\n';
ans.push_back(digit);
ans.push_back(n - digit);
}
}
bool isPlindrome(string s) {
string t = s;
reverse(t.begin(), t.end());
return (s == t);
}
void solve(ll n) {
if(n == 0) return;
if(isPlindrome(getString(n))) {
ans.push_back(n);
return;
}
if(n < 10) {
ans.push_back(n);
return;
}
if(n >= 10 && n < 100) {
for(int i = 1; i < 10; i++) {
if(isPlindrome(getString(n - i))) {
ans.push_back(i);
ans.push_back(n - i);
return;
}
}
}
auto cur = getString(n);
int sz = cur.size();
int midIdx = (sz - 1) / 2;
int idx = 0;
for(int i = midIdx; i >= 0; i--) {
if(cur[i] > '0') {
idx = i;
break;
}
}
if(idx == 0) {
solvePowerOf10((cur[0] - '0') * pw[sz - 1]);
solve(n - (cur[0] - '0') * pw[sz - 1]);
}
else if(isPlindrome(cur)) {
ans.push_back(n);
}
else {
ll toRem = 0;
for(int i = 0, power = (int) cur.size() - 1; i < idx; i++, power--) {
toRem += (cur[i] - '0' - (i == idx)) * (pw[power] + pw[i]);
}
toRem += (cur[idx] - '0' - 1) * pw[(int) cur.size() - 1 - idx];
if(sz % 2 == 0 || idx != midIdx) toRem += (cur[idx] - '0' - 1) * pw[idx];
ans.push_back(toRem);
solve(n - toRem);
}
}
// 544242542544
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
pw[0] = 1;
for(int i = 1; i <= 19; i++) pw[i] = 10 * pw[i - 1];
ll n;
cin >> n;
solve(n);
sort(ans.begin(), ans.end());
vector<ll> res = {ans[0]};
for(int i = 1; i < (int) ans.size(); i++) {
if(ans[i] + res.back() < 10) res.back() += ans[i];
else res.push_back(ans[i]);
}
cout << (int) res.size() << '\n';
for(auto i: res) cout << i << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3644kb
input:
1100000
output:
2 99999 1000001
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
1000
output:
2 1 999
result:
ok
Test #3:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
10
output:
2 1 9
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
11005
output:
3 5 999 10001
result:
ok
Test #5:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
100000000000000000
output:
2 1 99999999999999999
result:
ok
Test #6:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
21
output:
3 1 9 11
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
1234567887664321
output:
5 1 99 9889 110000011 1234567777654321
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
690231482249788720
output:
6 1 22 999 100001 1065555601 690231481184132096
result:
ok
Test #9:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
319173294485481281
output:
6 1 66 999 104401 1093003901 319173293392371913
result:
ok
Test #10:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
761353558778227546
output:
6 1 77 999 101101 1022772201 761353557755353167
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
947179993313410328
output:
6 1 77 999 104401 1013333101 947179992299971749
result:
ok
Test #12:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
171408535476134406
output:
6 1 33 999 108801 1040220401 171408534435804171
result:
ok
Test #13:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
896452012199589977
output:
6 1 77 999 104401 1089229801 896452011110254698
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
970894988875162603
output:
6 1 22 999 107701 1085555801 970894987789498079
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
200429647731477537
output:
6 1 33 999 107701 1084444801 200429646646924002
result:
ok
Test #16:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
960284896260606337
output:
5 2 979 12021 662111266 960284895598482069
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
999999999999999999
output:
1 999999999999999999
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1
output:
1 1
result:
ok
Test #19:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
7
output:
1 7
result:
ok
Test #20:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
487291873378192784
output:
1 487291873378192784
result:
ok
Test #21:
score: 0
Accepted
time: 2ms
memory: 3504kb
input:
414821987097225805
output:
6 4 11 111 16461 408080804 414821986689128414
result:
ok
Test #22:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
418581849637933703
output:
5 2 11 9889 789737987 418581848848185814
result:
ok
Test #23:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
607979478938276336
output:
5 11 727 182281 1163113611 607979477774979706
result:
ok
Test #24:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
471913902748260172
output:
5 11 101 52525 1638888361 471913901109319174
result:
ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1000003
output:
2 4 999999
result:
ok
Test #26:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
123456788654328
output:
4 7 999999 10000001 123456777654321
result:
ok