Submission #755434

#	Time	Username	Problem	Language	Result	Execution time	Memory
755434		dxz05	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	3 ms	360 KiB

numbers

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e6 + 3e2;

ll dp[18][2][11][11];
vector<int> digits;

ll calc(int ind, bool equal, int pre_last, int last){
    if (ind == digits.size()) return 1;

    ll &ans = dp[ind][equal][pre_last][last];
    if (ans != -1) return ans;

    ans = 0;

    for (int d = (ind == 0); d <= 9; d++){
        if (d == pre_last || d == last) continue;

        if (!equal || d < digits[ind]){
            ans += calc(ind + 1, false, last, d);
        } else if (d == digits[ind]){
            ans += calc(ind + 1, true, last, d);
        }
    }

    return ans;
}

ll f_fixed_length(ll n){
    if (n <= 9) return n + 1;

    memset(dp, -1, sizeof(dp));

    ll nn = n;

    digits.clear();
    while (nn > 0){
        digits.push_back(nn % 10);
        nn /= 10;
    }

    reverse(all(digits));

    return calc(0, true, 10, 10);
}

ll f(ll n){
    if (n <= 9) return n + 1;
    if (n == 1e18) --n;

    ll res = 0, pw = 9;
    while (pw < n){
        res += f_fixed_length(pw);
        pw = pw * 10 + 9;
    }

    res += f_fixed_length(n);

    return res;
}

void solve(){
    ll l, r;
    cin >> l >> r;

    ll ans = f(r);
    if (l) ans -= f(l - 1);

    cout << ans << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'll calc(int, bool, int, int)':
numbers.cpp:25:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if (ind == digits.size()) return 1;
      |         ~~~~^~~~~~~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:90:13: warning: unused variable 'startTime' [-Wunused-variable]
   90 |     clock_t startTime = clock();
      |             ^~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75