QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56706#3889. Balanced BreakdownSa3tElSefr#AC ✓2ms3732kbC++202.7kb2022-10-21 03:22:072022-10-21 03:22:07

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-10-21 03:22:07]
  • Judged
  • Verdict: AC
  • Time: 2ms
  • Memory: 3732kb
  • [2022-10-21 03:22:07]
  • Submitted

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;
}

详细

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