Submission #695366

#	Time	Username	Problem	Language	Result	Execution time	Memory
695366		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	384 KiB

numbers

#include <bits/stdc++.h>
#define ll long long
#define rep(i, n, m) for (ll i = n; i <= m; i ++)
#define rrep(i, n, m) for (ll i = n; i >= m; i --)
using namespace std;

string toString(ll x) {
    string ans;
    if (x == 0) return "0";
    while (x) ans += x % 10, x /= 10;
    reverse(ans.begin(), ans.end());
    return ans;
}

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

vector <int> num;

ll cal(ll pos, ll x1, ll x2, bool f, bool palin) {
    if (palin) return 0;
    if (pos == num.size()) return 1;

    ll &ret = dp[pos][x1 + 1][x2 + 1][f][palin];
    if (ret != -1) return ret;
    ret = 0;

    int lmt = num[pos];
    if (f) lmt = 9;

    rep(i, 0, lmt) {
        bool new_f = f;
        bool new_palin = palin;
        if (i < lmt) new_f = true;
        if (i == x2 || i == x1) new_palin = true;
        ret += cal(pos + 1, x2, (x2 == -1 && i == 0 ? -1 : i), new_f, new_palin);
    }
    return ret;
}


ll solve(ll x) {
    if (x == 0) return 1;
    if (x < 0) return 0;
    num.clear();
    while(x) num.push_back(x % 10), x /= 10;
    reverse(num.begin(), num.end());
    memset(dp, -1, sizeof dp);

    return cal(0, -1, -1, 0, 0);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen("B.inp", "r", stdin);
    //freopen("B.out", "w", stdout);

    ll a, b, ans = 0;
    cin >> a >> b;
    //cout << solve(b) << ' ' << solve(a - 1) << '\n';
    cout << solve(b) - solve(a - 1);

    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int cal(long long int, long long int, long long int, bool, bool)':
numbers.cpp:21:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (pos == num.size()) return 1;
      |         ~~~~^~~~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:59:14: warning: unused variable 'ans' [-Wunused-variable]
   59 |     ll a, b, ans = 0;
      |              ^~~

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