Submission #629910

#	Time	Username	Problem	Language	Result	Execution time	Memory
629910		typ_ik	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	424 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 = 25;
const int NUMBER_SIZE = 11;
const int WAS_SMALLER = 2;
const int POSITIVE = 2;

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

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 < WAS_SMALLER; w++)
                    for (int p = 0; p < POSITIVE; p++)
                    dp[i][pl][l][w][p] = -1;
}

vector <int> d;

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

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

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

    ll res = 0;

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

        bool currentSpace = (!nxt && !positive);

        res += get(pos + 1, (currentSpace ? 10 : l), (currentSpace ? 10 : nxt), was | (nxt < d[pos]), positive | (nxt > 0));
    }

    return dp[pos][pl][l][was][positive] = 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, 0);
    return dp[0][10][10][0][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, int)':
numbers.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if (pos == d.size())
      |         ~~~~^~~~~~~~~~~
numbers.cpp: At global scope:
numbers.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main() {
      | ^~~~

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