oj.uz

Submission #538689

# Submission time Handle Problem Language Result Execution time Memory
538689 2022-03-17T13:42:17 Z Lobo Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 20

ii n, a[maxn], b[maxn], mark[maxn][11][11][2][2][2];
ll dp[maxn][11][11][2][2][2];

ll sol(ii i, ii ant, ii act, ii pa, ii pb, ii zr) {
    if(i == n+1) return 1;

    if(mark[i][ant][act][pa][pb][zr]) return dp[i][ant][act][pa][pb][zr];

    mark[i][ant][act][pa][pb][zr] = 1;

    ll ans = 0;

    if(zr == 1 && a[i] == 0) {
        ans+= sol(i+1,10,10,0,1,1);
    }

    for(ii j = 0; j <= 9; j++) {
        if(zr == 1 && j == 0) continue;

        if(j == ant || j == act || (pa == 0 && j < a[i]) || (pb == 0 && j > b[i])) continue;
        ii npa = pa;
        if((a[i] != -1 && j > a[i]) || (a[i] == -1 && j > 0)) npa = 1;

        ii npb = pb;
        if(j < b[i]) npb = 1;

        ans+= sol(i+1,act,j,npa,npb,0);
    }

    //cout << i << " " << ant << " " << act << " " << pa << " " << pb << " " << zr << " == " << ans << endl;

    return dp[i][ant][act][pa][pb][zr] = ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    string sa,sb;
    cin >> sa >> sb;
    n = sb.size();
    reverse(all(sa));
    while(sa.size() < sb.size()) {
        sa+= '0';
    }
    reverse(all(sa));

    for(ii i = 1; i <= sb.size(); i++) {
        b[i] = sb[i-1]-'0';
    }

    for(ii i = 1; i <= sa.size(); i++) {
        a[i] = sa[i-1]-'0';
    }
    

    cout << sol(1,10,10,0,0,1) << endl;

}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:68:21: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(ii i = 1; i <= sb.size(); i++) {
      |                   ~~^~~~~~~~~~~~
numbers.cpp:72:21: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(ii i = 1; i <= sa.size(); i++) {
      |                   ~~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 0 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 328 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 452 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 456 KB Output is correct
34 Correct 1 ms 328 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 456 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 328 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 1 ms 452 KB Output is correct
44 Correct 1 ms 452 KB Output is correct
45 Correct 1 ms 468 KB Output is correct