QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#174496#1183. Sum of PalindromesSortingAC ✓177ms6700kbC++202.8kb2023-09-10 08:20:262023-09-10 08:20:26

Judging History

This is the latest submission verdict.

  • [2023-09-10 08:20:26]
  • Judged
  • Verdict: AC
  • Time: 177ms
  • Memory: 6700kb
  • [2023-09-10 08:20:26]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector<int> vi;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

int n ;
vector < int > v ;

vector < int > sub ( vector < int > up , vector < int > down ) {
    vector < int > ret ;
    reverse ( up.begin ( ) , up.end ( ) ) ;
    reverse ( down.begin ( ) , down.end ( ) ) ;
    while ( down.size ( ) < up.size ( ) ) { down.push_back ( 0 ) ; }
    int sz = up.size ( ) ;
    for ( int i = 0 ; i < sz ; ++ i ) {
        ret.push_back ( up[ i ] - down[ i ] ) ;
        while ( ret.back ( ) < 0 ) {
            ret.back ( ) += 10 ;
            -- up[ i + 1 ] ;
        }
    }
    while ( ret.empty ( ) == false && ret.back ( ) == 0 ) { ret.pop_back ( ) ; }
    reverse ( ret.begin ( ) , ret.end ( ) ) ;
    return ret ;
}

vector < vector < int > > ans ;

void solve ( ) {
    ans.clear ( ) ;
    string foo ; cin >> foo ;   
    n = foo.size ( ) ;
    v.clear ( ) ;
    for ( int i = 0 ; i < n ; ++ i ) {
        v.push_back ( ( foo[ i ] - '0' ) ) ;
    }
    while ( v.size ( ) > 0 ) {
        vector < int > cand ;
        n = v.size ( ) ;
        cand.resize ( n ) ;
        int mid = ( ( n - 1 ) / 2 ) ;
        for ( int i = 0 ; i <= mid ; ++ i ) {
            cand[ i ] = v[ i ] ;
        }
        for ( int i = mid + 1 ; i < n ; ++ i ) {
            cand[ i ] = cand[ n - i - 1 ] ;
        }
        bool ok = true ;
        for ( int i = 0 ; i < n ; ++ i ) {
            if ( cand[ i ] == v[ i ] ) { continue ; }
            if ( cand[ i ] > v[ i ] ) { ok = false ; }
            break ;
        }
        if ( ok == false ) {
            int pos = -1 ;
            for ( int i = mid ; i >= 0 ; -- i ) {
                if ( cand[ i ] > 0 ) { pos = i ; break ; }
            }
            if ( pos == 0 && cand[ 0 ] == 1 ) {
                cand.clear ( ) ;
                for ( int i = 0 ; i < n - 1 ; ++ i ) { cand.push_back ( 9 ) ; }
            }
            else {
                -- cand[ pos ] ;
                if ( pos != n - pos - 1 ) { 
                    -- cand[ n - pos - 1 ] ;
                }
                for ( int i = pos + 1 ; i < n - pos - 1 ; ++ i ) {
                    cand[ i ] = 9 ;
                }
            }
        }
        ans.push_back ( cand ) ;
        v = sub ( v , cand ) ;
    }
    int sz = ans.size ( ) ;
    cout << sz << "\n" ;
    for ( auto hh : ans ) {
        for ( auto x : hh ) {
            cout << x ;
        }
        cout << "\n" ;
    }
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

input:

2
378
2020

output:

2
373
5
3
2002
11
7

result:

ok OK!

Test #2:

score: 0
Accepted
time: 177ms
memory: 6700kb

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
11
9
3
11
9
1
1
22
2
22
1
2
22
2
2
22
3
2
22
4
2
22
5
2
22
6
2
22
7
2
22
8
2
22
9
3
22
9
1
1
33
2
33
1
2
33
2
2
33
3
2
33
4
2
33
5
2
33
6
2
33
7
2
33
8
2
33
9
3
33
9
1
1
44
2
44
1
2
44
2
2
44
3
2...

result:

ok OK!