Submission #869011

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

numbers

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN
#define M 1000000007 // 998244353

//digit dp
ll dp[20][2][13][13][2]; //also can have auxiliary info
string r;

constexpr ll INVALID = 10;

#define DP dp[pos][is_eq][l2][l1][lz]
ll solve(int pos, bool is_eq, ll l2, ll l1, ll lz) {
	if (~DP) return DP;
	if (pos==r.size())
		return DP=1;

	DP = 0;
	for (int i=0;i<=(is_eq?r[pos] - '0':9);i++){
        if (l1 == i) continue;
        if (l2 == i) continue;
        bool nlz = lz and !i;
        

        if (nlz) {
            assert(!i);
            DP += solve(pos+1, is_eq && i==r[pos] - '0', INVALID, INVALID, nlz);
        } else {    
            DP += solve(pos+1, is_eq && i==r[pos] - '0', l1, i,  nlz);
        }

        
        // if (i == 1) cout << "LOLLLLLLLL?? " << pos << " " << is_eq << " " << l2 << " " << l2 << " : " << DP << endl;
    }

	return DP;
}


int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    ll a,b;
    cin >> a >> b;
    ll lo=0;
    if (a ){
        
    memset(dp, -1, sizeof dp);
    r = to_string(a-1);
    lo = solve(0, 1, INVALID, INVALID, 1);
    }   

    // cout << "YO " << lo << endl;


    memset(dp, -1, sizeof dp);
    r = to_string(b);

    cout << solve(0, 1, INVALID, INVALID, 1)- lo << '\n';
}

Compilation message (stderr)

numbers.cpp: In function 'll solve(int, bool, ll, ll, ll)':
numbers.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  if (pos==r.size())
      |      ~~~^~~~~~~~~~

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