Submission #370353

#	Time	Username	Problem	Language	Result	Execution time	Memory
370353		ritul_kr_singh	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	492 KiB

numbers

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

vector<int> n;
int dp[10][10][20][2];

int solve(int x, int y, int pos, bool all){
    if(pos==n.size()) return 1;
    if(dp[x][y][pos][all]!=-1) return dp[x][y][pos][all];
    int res = 0;
    if(all){
        for(int i=0; i<10; ++i) if(i != x and i != y){
            res += solve(y, i, pos+1, true);
        }
    }else{
        for(int i=0; i<n[pos]; ++i) if(i != x and i != y){
            res += solve(y, i, pos+1, true);
        }
        if(n[pos] != x and n[pos] != y) res += solve(y, n[pos], pos+1, false);
    }
    return dp[x][y][pos][all] = res;
}

int ans(int num){
    if(num<=0) return num==0;
    for(int i=0;i<10; ++i)
        for(int j=0; j<10; ++j)
            for(int k=0; k<20; ++k)
                dp[i][j][k][0] = dp[i][j][k][1] = -1;
    n.clear();
    for(char c : to_string(num)) n.push_back(c-'0');
    int res = 0;
    for(int i=1; i<=n[0]; ++i) res += solve(i, i, 1, i!=n[0]);
    for(int l=2; l<=n.size(); ++l)
        for(int i=1; i<10; ++i)
            res += solve(i, i, l, true);
    return 1LL+res;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int a, b; cin >> a >> b;
//    cout << ans(321) nl;
    cout << ans(b) - ans(a-1);
}

Compilation message (stderr)

numbers.cpp: In function 'long long int solve(long long int, long long int, long long int, bool)':
numbers.cpp:12:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if(pos==n.size()) return 1;
      |        ~~~^~~~~~~~~~
numbers.cpp: In function 'long long int ans(long long int)':
numbers.cpp:38:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int l=2; l<=n.size(); ++l)
      |                  ~^~~~~~~~~~

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