oj.uz

Submission #859500

# Submission time Handle Problem Language Result Execution time Memory
859500 2023-10-10T09:00:28 Z kh0i Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 600 KB 
#include "bits/stdc++.h"
using namespace std;

#define F first
#define S second
#define sz(x) (int)((x).size())

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 0;
const int LG = __lg(N) + 1;
const int SQ = sqrt(N) + 1;
const ll mod = 1e9 + 7;

ll f[20][12][12][2][2];

ll go(string &s, int cur, int last1, int last2, int tight, int started){
    if(cur >= sz(s))
        return started;

    if(f[cur][last1][last2][tight][started] != -1)
        return f[cur][last1][last2][tight][started];

    ll res = 0;
    int mx = (tight ? s[cur] - '0' : 9);
    for(int nx = 0; nx <= mx; ++nx){
        if(started){
            if(nx == last1 or nx == last2)
                continue;
            res += go(s, cur + 1, last2, nx, (nx == mx ? tight : 0), 1);
        }
        else{
            if(nx == 0)
                res += go(s, cur + 1, 11, 11, 0, 0);
            else
                res += go(s, cur + 1, last2, nx, (nx == mx ? tight : 0), 1);
        }
    }
    return f[cur][last1][last2][tight][started] = res;
}

ll calc(string s){
    memset(f, -1, sizeof(f));
    return go(s, 0, 11, 11, 1, 0);
}

void solve(){
    ll l, r;
    cin >> l >> r;
    ll fi = calc(to_string(r));
    if(l > 0)
        fi -= calc(to_string(l - 1));
    else
        ++fi;
    cout << fi;
}


int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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