Submission #1332840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1332840		WongYiKai	Palindrome-Free Numbers (BOI13_numbers)	C++20	98.33 / 100	1 ms	344 KiB

numbers

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

ll dp[19][100];

ll cnt(ll a){
    if (a == 1e18) return cnt(a-1);
    if (a < 10) return a+1;
    ll x = 100;
    ll d = 2;
    ll ans = 10;
    while (a >= x){
        for (int i=10;i<100;i++){
            ans += dp[d][i];
        }
        x *= 10;
        d++;
    }
    x /= 100;
    ll curr = a/x;
    for (int i=10;i<curr;i++){
        ans += dp[d][i];
    }
    if (d==2) {
        ans += dp[d][curr];
        return ans;
    }
    ll pre = curr;
    if (pre%11 == 0) return ans;
    while (d>2){
        d -= 2;
        x /= 100;
        if (d>1) curr = (a/x)%100;
        else curr = a%10;
        for (int i=0;i<curr;i++){
            if (d==1){
                if (i != pre/10 && i != pre%10) ans += dp[d][i];
                continue;
            }
            if (i/10 == pre/10 || i/10 == pre%10 || pre%10 == i%10) continue;
            ans += dp[d][i];
        }
        if (d==1){
            if (curr != pre/10 && curr != pre%10) return ans+1;
        }
        if (d==2){
            if (curr/10 == pre/10 || curr/10 == pre%10 || pre%10 == curr%10) return ans;
            ans += dp[d][curr];
            return ans;
        }
        if (curr%11 == 0 || curr/10 == pre/10 || curr/10 == pre%10 || pre%10 == curr%10) return ans;
        pre = curr;
    }

}

int main(){
    ll a,b;
    cin >> a >> b;
    for (int i=0;i<10;i++) dp[1][i] = 1;
    for (int i=0;i<100;i++){
        if (i%11 != 0) dp[2][i] = 1;
        else dp[2][i] = 0;
    }
    for (int i=3;i<=18;i++){
        for (int j=0;j<100;j++){
            if (j%11 == 0){
                dp[i][j] = 0;
                continue;
            }
            dp[i][j] = 0;
            for (int k=0;k<10;k++){
                if (k != j/10) dp[i][j] += dp[i-1][j%10*10+k];
            }
        }
    }
    cout << cnt(b)-cnt(a-1);
}

Compilation message (stderr)

numbers.cpp: In function 'll cnt(ll)':
numbers.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^

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