Submission #856988

#	Time	Username	Problem	Language	Result	Execution time	Memory
856988		MrMody	Palindrome-Free Numbers (BOI13_numbers)	C++17	73.75 / 100	1 ms	604 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el "\n"
#define fio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

vector<int> num;
ll DP[21][11][11][2];

ll cnt(int pos,int i_1,int i__2,bool f){
    if(pos == num.size()){
        return 1;
    }
    
    ll &ret = DP[pos][i_1][i__2][f];
    if(ret == -1){
        ret = 0;
        int limit = 9;
        if(!f){
            limit = num[pos];
        }
        for(int d=0;d<=limit;++d){
            bool new_f = f || (d < limit);
            if(d != i_1 && d != i__2){
                ret += cnt(pos+1,d,i_1,new_f);
            }
        }
    }
    return ret;
}

ll solve(ll x){
    if(x < 0)
        return 0;
    if(x == 0)
        return 1;
    num.clear();
    while(x > 0){
        num.push_back(x%10);
        x/=10;
    }
    assert(num.size() > 0);
    reverse(num.begin(), num.end());
    memset(DP, -1, sizeof(DP));
    return cnt(0, 10, 10, 0) + (num.size() > 1);
}


void solve() {
    ll a,b;
    cin >> a >> b;
    cout << solve(b) - solve(a-1);
}

int main() {
    fio
    int tc{ 1 };
    // cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'll cnt(int, int, int, bool)':
numbers.cpp:11:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     if(pos == num.size()){
      |        ~~~~^~~~~~~~~~~~~

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