Submission #1211544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211544		i_love_spring	Palindrome-Free Numbers (BOI13_numbers)	C++20	32.50 / 100	1100 ms	74648 KiB

numbers

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using ti = tuple<int, bool, bool, vector<int>>;

map<tuple<int, bool, bool, vector<int>>, ll> memo;

bool is_palindrome(const vector<int>& seq, int start, int len) {
    int end = start + len - 1;
    while (start < end) {
        if (seq[start] != seq[end]) return false;
        ++start; --end;
    }
    return true;
}

bool contains_palindrome(const vector<int>& suffix) {
    int L = suffix.size();
    for (int len = 2; len <= L; ++len) {
        for (int i = 0; i + len <= L; ++i) {
            if (is_palindrome(suffix, i, len))
                return true;
        }
    }
    return false;
}

ll dp(const vector<int>& digits, int pos, bool tight, bool leading_zero, vector<int> last_digits) {
    if (pos == digits.size()) return 1;

    ti state = make_tuple(pos, tight, leading_zero, last_digits);
    if (memo.count(state)) return memo[state];

    int limit = tight ? digits[pos] : 9;
    ll res = 0;

    for (int d = 0; d <= limit; ++d) {
        bool new_tight = tight && (d == limit);
        bool new_leading_zero = leading_zero && (d == 0);
        vector<int> new_last_digits = last_digits;

        if (!new_leading_zero) {
            new_last_digits.push_back(d);
            if (new_last_digits.size() > 6)
                new_last_digits.erase(new_last_digits.begin());

            if (contains_palindrome(new_last_digits))
                continue;
        }

        res += dp(digits, pos + 1, new_tight, new_leading_zero, new_last_digits);
    }

    return memo[state] = res;
}

ll count_palindrome_free_up_to(ll n) {
    memo.clear();
    if (n < 0) return 0;

    vector<int> digits;
    while (n > 0) {
        digits.push_back(n % 10);
        n /= 10;
    }
    if (digits.empty()) digits.push_back(0);
    reverse(digits.begin(), digits.end());

    return dp(digits, 0, true, true, {});
}

ll count_palindrome_free_range(ll a, ll b) {
    return count_palindrome_free_up_to(b) - count_palindrome_free_up_to(a - 1);
}

int main() {
    ll a, b;
    cin >> a >> b;

    cout << count_palindrome_free_range(a, b) << '\n';
    return 0;
}

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