Submission #899637

#	Time	Username	Problem	Language	Result	Execution time	Memory
899637		wksp	Palindrome-Free Numbers (BOI13_numbers)	C++14	20 / 100	1 ms	504 KiB

numbers

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


long long dp[25][11]; // position, letter (0-9)
long long dp_static[25][11];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    long long a, b;
    cin >> a >> b;
    a--;
    vector<int> a_ve;
    vector<int> b_ve;
    while(a > 0){
        a_ve.push_back(a%10);
        a /= 10;
    }
    while(b > 0){
        b_ve.push_back(b%10);
        b /= 10;
    }
    reverse(a_ve.begin(), a_ve.end());
    reverse(b_ve.begin(), b_ve.end());
    for(int i = 0; i < 10; i++){
        dp[1][i] = i;
        dp_static[1][i] = 1;
    }
    for(int i = 2; i < 20; i++){
        dp[i][0] = dp[i-1][9] - dp_static[i-1][0];
        dp_static[i][0] = dp[i][0];
        for(int j = 1; j < 10; j++){
            dp_static[i][j] = dp[i][0] - dp_static[i-1][j] - dp_static[i-2][j];
            dp[i][j] = dp[i][j-1] + dp_static[i][j]; 
        }
    }
    int last = -1;
    int last_second = -1;
    int nr = a_ve.size() + 1;
    long long ans_a = 0;
    bool update = true;
    for(auto u: a_ve){
        nr--;
        if(last == u or last_second == u){
            update = false;
            break;
        }
        if(u == 0){
            last_second = last;
            last = u;
            continue;
        }
        ans_a += dp[nr][u-1];
        if(last != -1){
            ans_a -= dp_static[nr-1][last];
        }
        if(last != -1 and last < u){
            ans_a -= dp_static[nr][last];
        }
        if(last_second != -1 and last_second < u){
            ans_a -= dp_static[nr][last_second];
        }

        last_second = last;
        last = u;
    }
    if(update){
        ans_a++;
    }   
    update = true;
    last = -1;
    last_second = -1;
    nr = b_ve.size() + 1;
    long long ans_b = 0;
    for(auto u: b_ve){
        nr--;
        if(last == u or last_second == u){
            update = false;
            break;
        }
        if(u == 0){
            last_second = last;
            last = u;
            continue;
        }
        ans_b += dp[nr][u-1];
        if(last != -1){
            ans_b -= dp_static[nr-1][last];
        }
        if(last != -1 and last < u){
            ans_b -= dp_static[nr][last];
        }
        if(last_second != -1 and last_second < u){
            ans_b -= dp_static[nr][last_second];
        }

        last_second = last;
        last = u;
    }
    if(update){
        ans_b++;
    }
    long long ans = ans_b - ans_a;
    cout << ans << '\n';





    return 0;
}

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