Submission #1255335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255335		MisterReaper	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	0 ms	328 KiB

numbers

// File T.cpp created on 09.08.2025 at 00:30:11
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int M = 19;

i64 pow10[M];

i64 f(i64 n) {
    i64 dp[11][11][2] {};
    dp[10][10][0] = 1;
    for (int i = M - 1; i >= 0; --i) {
        i64 ndp[11][11][2] {};
        for (int j = 0; j <= 10; ++j) {
            for (int k = 0; k <= 10; ++k) {
                for (int l = 0; l < 2; ++l) {
                    if (dp[j][k][l] == 0) {
                        continue;
                    }
                    int bound = (l == 1 ? 9 : int(n / pow10[i] % 10));
                    for (int p = 0; p <= bound; ++p) {
                        if (k != 10 && (p == j || p == k)) {
                            continue;
                        }
                        if (k == 10 && p == 0) {
                            ndp[10][10][l || p != bound] += dp[j][k][l];
                        } else {
                            ndp[k][p][l || p != bound] += dp[j][k][l];
                        }
                    }
                }
            }
        }
        std::swap(dp, ndp);
    }
    i64 res = 0;
    for (int i = 0; i <= 10; ++i) {
        for (int j = 0; j <= 10; ++j) {
            res += dp[i][j][0] + dp[i][j][1];
        }
    }
    return res;
}

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

    pow10[0] = 1;
    for (int i = 0; i < M - 1; ++i) {
        pow10[i + 1] = pow10[i] * 10;
    }

    i64 A, B;
    std::cin >> A >> B;

    i64 ans = f(B) - f(A - 1);
    std::cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

numbers.cpp:14:5: warning: built-in function 'pow10' declared as non-function [-Wbuiltin-declaration-mismatch]
   14 | i64 pow10[M];
      |     ^~~~~

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