Submission #1255264

#TimeUsernameProblemLanguageResultExecution timeMemory
1255264EkinOnalPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
0 ms328 KiB
//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define pb push_back
#define int long long
#define vi vector<int>


int a,b; vi dp(22),dp2(22),pre(22),uson(22);
int f(int kalan,int mx,int lst1, int lst2,bool ilk){
	if(kalan==0) return 0;

	// cout<<kalan<<" "<<mx<<" "<<lst1<<" "<<lst2<<" : \n";

	vi to_go; 
	for(int i=0;i<=min(9ll,mx/uson[kalan-1]);i++){
		if(i!=lst1 && i!=lst2 && !(i==0 && ilk) ) to_go.pb(i);
	}

	if(to_go.size()==0) return 0;
	if(kalan==1) {return (int)to_go.size();} 

	int ans= ((int)to_go.size()-1) * (ilk ? dp2[kalan-1] : dp[kalan-1]) ;

	if(to_go[(int)to_go.size()-1]!=mx/uson[kalan-1]) ans += ( ilk ? dp2[kalan-1] : dp[kalan-1] );
	else{
		if(lst2==-1) lst2=mx/uson[kalan-1];
		else if(lst1==-1) lst1=lst2,lst2=mx/uson[kalan-1];
		else lst1=lst2,lst2=mx/uson[kalan-1];

		ans += f(kalan-1,mx%uson[kalan-1],lst1,lst2,0);
	}

	return ans;
}	
	
	
void solve(){
	cin>>a>>b;

	if(a==b && a==0){
		cout<<"1\n"; return;
	}

	dp[0]=1; dp[1]=8; dp[2]=64;
	dp2[0]=1; dp2[1]=9; dp2[2]=72; pre[0]=1; pre[1]=9+pre[0]; pre[2]=pre[1]+81; int tmp=9*9*8;
	for(int i=3;i<=18;i++){
		dp[i]=dp[i-1]*8, dp2[i]=dp2[i-1]*8, 
		pre[i]=pre[i-1]+tmp;
		tmp*=8;
	}

	int len1=0,len2=0, 
	curr=b;
	while(curr) len2++,curr/=10;

	if(!a){
		int cvp=f(len2,b,-1,-1,1)+pre[len2-1];
		cout<<cvp<<endl;
		return;
	}

	a--;
	curr=a;
	while(curr) len1++,curr/=10;

	// cout<<len1<<" "<<len2<<endl;
	if(a==0){
		cout<<f(len2,b,-1,-1,1)+pre[len2-1]-1<<endl;
		return;
	}

	// cout<<len1<<" "<<len2<<endl;

	int cvp=f(len2,b,-1,-1,1)-f(len1,a,-1,-1,1)-pre[len1-1]+pre[len2-1];
	cout<<cvp<<endl;
}	
	
int32_t main(/*	int32_t argc, char* argv[]*/){
	std::ios_base::sync_with_stdio(0); std::cin.tie(0);	

	uson[0]=1;
	for(int i=1;i<=18;i++) uson[i]=uson[i-1]*10;

		// cout<<((int)1e18)<<endl;

	int t=1;
	// cin >> t;
	while (t--) solve();
 	
	return 0;
}	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...