Submission #467017

#	Time	Username	Problem	Language	Result	Execution time	Memory
467017		ezdp	Palindrome-Free Numbers (BOI13_numbers)	C++14	95 / 100	1 ms	332 KiB

numbers

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

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define bit(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are smaller than x
/// insert(x)		 -> inserts x into the set

string n;
ll dp[19][11][11][2][2];

ll f(ll len = 0, ll prv1 = 10, ll prv2 = 10, bool flag = 0, bool pass = 0){
	if(len == n.size()){
		return 1;
	}
	if(dp[len][prv1][prv2][flag][pass] != -1)
		return dp[len][prv1][prv2][flag][pass];
	ll ret = 0, limit = (flag ? 9 : n[len] - '0');
	for(int dgt = 0; dgt <= limit; dgt ++){
		if(dgt == prv1 || dgt == prv2) continue;
		
		bool new_flag = flag;
		bool new_pass = pass;
		
		if(dgt < limit) new_flag = true;
		if(dgt) new_pass = 1;
		
		ret += f(len + 1, (new_pass ? prv2 : 10), (new_pass ? dgt : 10), new_flag, new_pass);
	}
	return dp[len][prv1][prv2][flag][pass] = ret;
}

ll s(ll x){
	n.clear();
	while(x){
		n += (char)((x % 10) + '0');
		x /= 10;
	}
	reverse(all(n));
	memset(dp, -1, sizeof(dp));
	return (n.empty() ? 0 : f());
}

int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll a, b; cin >> a >> b;
	cout << (a ? s(b) - s(a - 1) : s(b)) << endl;
}
/**

*/

Compilation message (stderr)

numbers.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
numbers.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
numbers.cpp: In function 'long long int f(long long int, long long int, long long int, bool, bool)':
numbers.cpp:33:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  if(len == n.size()){
      |     ~~~~^~~~~~~~~~~

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