Submission #1244355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244355		eirinayukari	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	584 KiB

numbers

// XD XD
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el cout << "\n";

using namespace std;
using ll = long long;

const int MAXN = 1e6 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e18 + 7;

template <typename T>
bool ckmin(T& a, T b) {
    return a > b ? a = b, true : false;
}

template <typename T>
bool ckmax(T& a, T b) {
    return a < b ? a = b, true : false;
}

string A, B;
ll dp[20][2][2][2][11][11];
ll dfs(int pos, bool bgr, bool sml, bool lead, int last1, int last2) {
    if (pos == A.size()) {
        return 1;
    }
    ll &ret = dp[pos][bgr][sml][lead][last1][last2];
    if (ret != -1) {
        return ret;
    }
    ret = 0;
    int x = A[pos] - '0';
    int y = B[pos] - '0';
    int l = bgr ? 0 : x;
    int r = sml ? 9 : y;
    
    for (int d = l; d <= r; d++) {
        bool nbgr = bgr || (d > x);
        bool nsml = sml || (d < y);
        bool nlead = lead && (d == 0);
        int nlast1 = last1, nlast2 = last2;
        if (!nlead) {
            if (d == last1 || d == last2) {
                continue;
            }
            nlast2 = last1;
            nlast1 = d;
        }
        ret += dfs(pos + 1, nbgr, nsml, nlead, nlast1, nlast2);
    }
    return ret;
}

void solve(int id) {
    // cout << "Case " << id << ": ";    
    cin >> A >> B;
    while (A.size() < B.size()) {
        A = "0" + A;
    }
    
    memset(dp, -1, sizeof dp);
    cout << dfs(0, false, false, true, 10, 10) << "\n";
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

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