QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#57987#3889. Balanced BreakdownBeevo#AC ✓3ms3732kbC++231.7kb2022-10-24 03:46:522022-10-24 03:46:55

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-24 03:46:55]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 3732kb
  • [2022-10-24 03:46:52]
  • Submitted

answer

#include <bits/stdc++.h>

#define el '\n'
#define ll long long
#define ld long double

#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

ll pw[20];

void pre() {
    pw[0] = 1;

    for (int i = 1; i < 19; i++)
        pw[i] = pw[i - 1] * 10;
}

bool palindrome(string &s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != s[s.size() - i - 1])
            return 0;
    }

    return 1;
}

string closestPalindrome(string &s) {
    if (palindrome(s))
        return s;

    int n = s.size();

    if (count(s.begin(), s.end(), '0') == n - 1 && s[0] == '1')
        return max(string(n - 1, '9'), string("0"));

    string t = "0";
    for (int l = 0; l < n; l++) {
        ll x = stoll(s) - pw[n - l - 1];

        string cur = to_string(x);

        for (int i = 0; i < (n + 1) / 2; i++) {
            if (i > l)
                cur[i] = cur[n - i - 1] = '9';
            else {
                if (n - i - 1 > l)
                    cur[n - i - 1] = cur[i];
                else
                    cur[i] = cur[n - i - 1] = min(cur[i], cur[n - i - 1]);
            }
        }

        if (stoll(cur) > stoll(t))
            t = cur;
    }

    return t;
}

void testCase() {
    pre();

    string s;
    cin >> s;

    vector<string> v;

    while (s != "0") {
        v.push_back(closestPalindrome(s));

        s = to_string(stoll(s) - stoll(v.back()));
    }

    cout << v.size() << el;

    for (auto i: v)
        cout << i << el;
}

signed main() {
    Beevo

    int T = 1;
//    cin >> T;

    while (T--)
        testCase();

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3700kb

input:

1100000

output:

2
1099901
99

result:

ok 

Test #2:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

1000

output:

2
999
1

result:

ok 

Test #3:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

10

output:

2
9
1

result:

ok 

Test #4:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

11005

output:

3
10901
101
3

result:

ok 

Test #5:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

100000000000000000

output:

2
99999999999999999
1

result:

ok 

Test #6:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

21

output:

3
11
9
1

result:

ok 

Test #7:

score: 0
Accepted
time: 2ms
memory: 3684kb

input:

1234567887664321

output:

3
1234567887654321
9999
1

result:

ok 

Test #8:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

690231482249788720

output:

7
690231481184132096
1065555601
100001
1001
11
9
1

result:

ok 

Test #9:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

319173294485481281

output:

7
319173293392371913
1093003901
104401
1001
55
9
1

result:

ok 

Test #10:

score: 0
Accepted
time: 2ms
memory: 3680kb

input:

761353558778227546

output:

7
761353557755353167
1022772201
101101
1001
66
9
1

result:

ok 

Test #11:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

947179993313410328

output:

7
947179992299971749
1013333101
104401
1001
66
9
1

result:

ok 

Test #12:

score: 0
Accepted
time: 2ms
memory: 3660kb

input:

171408535476134406

output:

7
171408534435804171
1040220401
108801
1001
22
9
1

result:

ok 

Test #13:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

896452012199589977

output:

7
896452011110254698
1089229801
104401
1001
66
9
1

result:

ok 

Test #14:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

970894988875162603

output:

7
970894987789498079
1085555801
107701
1001
11
9
1

result:

ok 

Test #15:

score: 0
Accepted
time: 2ms
memory: 3680kb

input:

200429647731477537

output:

7
200429646646924002
1084444801
107701
1001
22
9
1

result:

ok 

Test #16:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

960284896260606337

output:

5
960284895598482069
662121266
2992
9
1

result:

ok 

Test #17:

score: 0
Accepted
time: 2ms
memory: 3712kb

input:

999999999999999999

output:

1
999999999999999999

result:

ok 

Test #18:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

1

output:

1
1

result:

ok 

Test #19:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

7

output:

1
7

result:

ok 

Test #20:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

487291873378192784

output:

1
487291873378192784

result:

ok 

Test #21:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

414821987097225805

output:

5
414821986689128414
408090804
6556
22
9

result:

ok 

Test #22:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

418581849637933703

output:

5
418581848848185814
789737987
9889
11
2

result:

ok 

Test #23:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

607979478938276336

output:

5
607979478874979706
63288236
8338
55
1

result:

ok 

Test #24:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

471913902748260172

output:

5
471913902209319174
538939835
1111
44
8

result:

ok 

Test #25:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

1000003

output:

2
1000001
2

result:

ok 

Test #26:

score: 0
Accepted
time: 2ms
memory: 3728kb

input:

123456788654328

output:

3
123456787654321
1000001
6

result:

ok