Submission #1333942

#TimeUsernameProblemLanguageResultExecution timeMemory
1333942gelastropodPalindrome-Free Numbers (BOI13_numbers)C++20
50 / 100
1 ms352 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;

string s;

vector<vector<vector<long long>>> mem, mem1;

long long dp(int n, int d1, int d2) {
    if (n == -1) return 0;
    if (mem[n][d1][d2] != -1) return mem[n][d1][d2];
    long long res = 0;
    for (int i = 0; i < 10; i++) {
        if (i == d1 || i == d2) res += pow(10, n);
        else res += dp(n - 1, i, d1);
    }
    return mem[n][d1][d2] = res;
}

long long dp1(int n, int d1, int d2) {
    if (d1 == 0 && d2 == 10) d1 = 10;
    if (n == -1) return 0;
    if (mem1[n][d1][d2] != -1) return mem1[n][d1][d2];
    long long res = 0;
    for (int i = 0; i < s[n] - '0'; i++) {
        if (i == d1 || i == d2) res += pow(10, n);
        else res += dp(n - 1, i, d1);
    }
    if (s[n] - '0' == d1 || s[n] - '0' == d2) {
        string s1 = (n == 0 ? "1" : s.substr(0, n));
        reverse(s1.begin(), s1.end());
        res += stoll(s1);
    }
    else res += dp1(n - 1, s[n] - '0', d1);
    return mem1[n][d1][d2] = res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    mem.resize(18, vector<vector<long long>>(11, vector<long long>(11, -1)));
    mem1.resize(18, vector<vector<long long>>(11, vector<long long>(11, -1)));
    long long n1, n2;
    cin >> n1; n1--;
    s = to_string(max(0LL, n1));
    reverse(s.begin(), s.end());
    int s1 = s.size();
    s += string(20 - s.size(), ':');
    long long res1 = dp1(s1 - 1, 10, 10);
    for (int i = 0; i < 18; i++) for (int j = 0; j < 11; j++) for (int k = 0; k < 11; k++) mem[i][j][k] = mem1[i][j][k] = -1;
    cin >> s;
    n2 = stoll(s);
    reverse(s.begin(), s.end());
    s1 = s.size();
    s += string(20 - s.size(), ':');
    long long res2 = dp1(s1 - 1, 10, 10);
    cout << n2 - n1 - res2 + res1 << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...