oj.uz

Submission #873740

# Submission time Handle Problem Language Result Execution time Memory
873740 2023-11-15T15:08:31 Z fryingduc Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 3 ms 1884 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

#define int long long

const int maxn = 25;
int n, f[25][12][12][2][25];

int go(string &s, int id, int l1, int l2, bool tight, int started){
    if(id == (int)s.size()){
        return 1;
    }
    if(f[id][l1][l2][tight][started] != -1) return f[id][l1][l2][tight][started];
    
    int bound = 9, res = 0;
    if(tight) bound = (s[id] - '0');
    for(int i = 0; i <= bound; ++i){
        if(i == l1 || i == l2) continue;
        bool niu_tight = (i == bound ? tight : 0);
        int niu_started = (i == 0 and started == 0 ? 0 : started + 1);
        res += go(s, id + 1, (niu_started ? i : 10), (niu_started > 1 ? l1 : 10) , niu_tight, niu_started);
    }
    return f[id][l1][l2][tight][started] = res;
}
int calc(int x){
    string s = to_string(x);
    memset(f, -1, sizeof(f)); 
    return go(s, 0, 10, 10, 1, 0);
}
void solve(){
    int l, r; cin >> l >> r;
    debug(calc(r), calc(l - 1));
    cout << calc(r) - calc(l - 1);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int test = 1;
    // cin >> test;
    for(int i = 1; i <= test; i++){
      // cout << "Case " << "#" << i << ": "; 
      solve();
    }

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1696 KB Output is correct
8 Correct 1 ms 1624 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 1 ms 1628 KB Output is correct
15 Correct 1 ms 1880 KB Output is correct
16 Correct 1 ms 1628 KB Output is correct
17 Correct 1 ms 1628 KB Output is correct
18 Correct 1 ms 1628 KB Output is correct
19 Correct 2 ms 1628 KB Output is correct
20 Correct 1 ms 1628 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 2 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1884 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 1 ms 1628 KB Output is correct
15 Correct 1 ms 1628 KB Output is correct
16 Correct 2 ms 1628 KB Output is correct
17 Correct 2 ms 1864 KB Output is correct
18 Correct 2 ms 1632 KB Output is correct
19 Correct 2 ms 1636 KB Output is correct
20 Correct 2 ms 1632 KB Output is correct
21 Correct 2 ms 1752 KB Output is correct
22 Correct 2 ms 1632 KB Output is correct
23 Correct 2 ms 1636 KB Output is correct
24 Correct 2 ms 1628 KB Output is correct
25 Correct 2 ms 1632 KB Output is correct
26 Correct 2 ms 1868 KB Output is correct
27 Correct 2 ms 1816 KB Output is correct
28 Correct 2 ms 1628 KB Output is correct
29 Correct 2 ms 1628 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct
31 Correct 2 ms 1628 KB Output is correct
32 Correct 2 ms 1628 KB Output is correct
33 Correct 2 ms 1748 KB Output is correct
34 Correct 2 ms 1628 KB Output is correct
35 Correct 2 ms 1628 KB Output is correct
36 Correct 2 ms 1628 KB Output is correct
37 Correct 2 ms 1628 KB Output is correct
38 Correct 2 ms 1628 KB Output is correct
39 Correct 3 ms 1628 KB Output is correct
40 Correct 2 ms 1628 KB Output is correct
41 Correct 3 ms 1628 KB Output is correct
42 Correct 2 ms 1628 KB Output is correct
43 Correct 2 ms 1628 KB Output is correct
44 Correct 2 ms 1628 KB Output is correct
45 Correct 2 ms 1628 KB Output is correct