Submission #859500

#	Time	Username	Problem	Language	Result	Execution time	Memory
859500		kh0i	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	600 KiB

numbers

#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 / 25
• Subtask 2: 75 / 75