Submission #1120611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120611		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	2 ms	512 KiB

numbers

#include <bits/stdc++.h>
#define ll long long
#define mein ios::base_sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

ll dp[10][10][20][2];
string str;
ll cal(int f, int s, int len, bool l){
    if(len >= str.length()){
        return 1;
    }
    else{
        if(dp[f][s][len][l] == -1){
            ll check = 0;
            if(l){
                for(int i = 0; i <= 9; ++i){
                    if(i != f && i != s){
                        check +=cal(s,i,len+1,true);
                    }
                }
            }
            else{
                int border = str[len] - '0';
                for(int i = 0; i < border; ++i){
                    if(i != f && i != s){
                        check +=cal(s,i,len+1,true);
                    }
                }
                if(border != f && border != s){
                    check += cal(s,border,len+1,false);
                }
            }
            dp[f][s][len][l] = check;
        }
        return dp[f][s][len][l];
    }
}

ll memory(ll num){
    if(num < 0) return 0;
    stringstream ss; ss << num;
    str = ss.str();
    memset(dp, -1, sizeof(dp));
    int f = str[0] - '0';
    ll ans = 1;
    for(int i = 1; i <= f; ++i){
        ans += cal(i,i,1,i != f);
    }
    for(int j = 2; j <= str.length(); ++j){
        for(int i = 1; i < 10; ++i){
            ans += cal(i,i,j,true);
        }
    }
    return ans;
}

int main(){
    ll a,b;
    cin >> a >> b;
    ll x = memory(b) - memory(a-1);
    cout << x << endl;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int cal(int, int, int, bool)':
numbers.cpp:9:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     if(len >= str.length()){
      |        ~~~~^~~~~~~~~~~~~~~
numbers.cpp: In function 'long long int memory(long long int)':
numbers.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int j = 2; j <= str.length(); ++j){
      |                    ~~^~~~~~~~~~~~~~~

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