Submission #1299038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299038		daotuankhoi	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	640 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long

template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }

int d[20];
ll dp[20][11][11][2];

ll solve(int pos, int tight, int l1, int l2, bool start) {
    if (pos < 0) return 1;
    if (!tight && dp[pos][l1][l2][start] != -1) return dp[pos][l1][l2][start];
    ll res = 0;
    int lim = tight ? d[pos] : 9;
    for (int i = 0; i <= lim; i++) {
        if (i != l1 && i != l2) {
            bool nx = start || i > 0;
            res += solve(pos - 1, tight && i == lim, (nx ? l2 : 10), (nx ? i : 10), nx);
        }
    }
    if (!tight) dp[pos][l1][l2][start] = res;
    return res;
}

ll calc(ll x) {
    if (x < 0) return 0;
    int n = 0;
    d[0] = 0;
    while (x) {
        d[n++] = x % 10;
        x /= 10;
    }
    return solve(n - 1, 1, 10, 10, 0);
}

int main() {
    #define NAME "test"
    if (fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dp, -1, sizeof dp);
    ll l, r; cin >> l >> r;
    cout << calc(r) - calc(l - 1) << '\n';
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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