Submission #629896

#	Time	Username	Problem	Language	Result	Execution time	Memory
629896		typ_ik	Palindrome-Free Numbers (BOI13_numbers)	C++17	37.50 / 100	2 ms	340 KiB

numbers

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " = " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;

const int LEN = 20;
const int NUMBER_SIZE = 11;
const int WAS_SMALLER = 2;

ll dp[LEN][NUMBER_SIZE][NUMBER_SIZE][WAS_SMALLER];

void init() {
    for (int i = 0; i < LEN; i++)
        for (int pl = 0; pl < NUMBER_SIZE; pl++)
            for (int l = 0; l < NUMBER_SIZE; l++)
                for (int w = 0; w < 2; w++)
                    dp[i][pl][l][w] = -1;
}

vector <int> d;

ll get(int pos, int pl, int l, int was) {
    if (pos == d.size())
        return dp[pos][pl][l][was] = 1;

    if (dp[pos][pl][l][was] != -1)
        return dp[pos][pl][l][was];

    int mx = d[pos];
    if (was)
        mx = 9;

    int res = 0;

    for (int nxt = 0; nxt <= mx; nxt++) {
        if (nxt == pl || nxt == l)
            continue;

        res += get(pos + 1, l, nxt, was | (nxt < d[pos]));
    }

    return dp[pos][pl][l][was] = res;
}

ll calc(ll x) {
    d.clear();
    while (x) d.push_back(x % 10), x /= 10;
    reverse(all(d));
    init();
    get(0, 10, 10, 0);
    return dp[0][10][10][0];
}

void solve() {
    ll a, b;
    cin >> a >> b;
    cout << calc(b) - calc(a - 1) << '\n';
}

main() {
    boost;
    solve();
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int get(int, int, int, int)':
numbers.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if (pos == d.size())
      |         ~~~~^~~~~~~~~~~
numbers.cpp: At global scope:
numbers.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 | main() {
      | ^~~~

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