Submission #1255159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255159		EkinOnal	Palindrome-Free Numbers (BOI13_numbers)	C++20	72.50 / 100	1096 ms	328 KiB

numbers

//#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 MAX 1000023
#define pb push_back
// #define mp make_pair 
#define int long long
#define f first
#define s second
#define vi vector<int>
#define pii pair<int,int>
#define si set<int>
#define vpii vector<pair<int,int>> 
const int mod = 998244353;
const int INF = 1e18+1;
// myMap.begin()->first :  key
// myMap.begin()->second : value
 
int epow(int a,int b){int ans=1;while(b){if(b&1) ans*=a;a*=a;b>>=1;}return ans;}
int gcd(int a,int b) {if(a<b)swap(a,b);while(b){int tmp=b;b=a%b;a=tmp;}return a;}
int mul(int a,int b){return ((a%mod)*(b%mod)+mod)%mod;}
int sum(int a,int b){return ((a%mod)+(b%mod)+mod)%mod;}
// typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
// typedef
// tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_multiset	
	
int a,b; vi dp(22),dp2(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/(epow(10,kalan-1)));i++){
		if(i!=lst1 && i!=lst2 && !(i==0 && ilk) ) to_go.pb(i);
	}

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

	int ans=0;
	for(int i=0;i<to_go.size()-1;i++){
		ans += ( ilk ? dp2[kalan-1] : dp[kalan-1] );
	}
	if(to_go[to_go.size()-1]!=mx/(epow(10,kalan-1))) ans += ( ilk ? dp2[kalan-1] : dp[kalan-1] );
	else{
		if(lst2==-1) lst2=mx/(epow(10,kalan-1));
		else if(lst1==-1) lst1=lst2,lst2=mx/(epow(10,kalan-1));
		else lst1=lst2,lst2=mx/(epow(10,kalan-1));

		ans += f(kalan-1,mx%(epow(10,kalan-1)),lst1,lst2,0);
	}
	//cout<<to_go.size()<<endl;

	//cout<<kalan<<" "<<tight<<" "<<mx<<" "<<lst1<<" "<<lst2<<" : "<<ans<<endl;
//	cout<<ans<<endl;

	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;
	for(int i=3;i<=18;i++) dp[i]=dp[i-1]*8, dp2[i]=dp2[i-1]*8;

//	cout<<f(3,321,-1,-1,1)-f(3,122,-1,-1,1)<<endl;
//	f(3,321,-1,-1,1);

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

	if(!a){
		int cvp=0;
		for(int i=1;i<len2;i++) cvp+=dp2[i];

		cvp+=f(len2,b,-1,-1,1)+1 ;//- f(len2-1,epow(10,len2-1)-1,-1,-1,1);	
		cout<<cvp<<endl;
		return;
	}


	if(len1==len2){
		cout<<f(len1,b,-1,-1,1) - ( a!=epow(10,len1-1) ?  f(len1,a-1,-1,-1,1) : 0ll);
		return;
	}


	int cvp= f(len1,epow(10,len1)-1,-1,-1,1) - ( a!=epow(10,len1-1) ?  f(len1,a-1,-1,-1,1) : 0ll);
	cvp += f(len2,b,-1,-1,1) ;

	for(int i=len1+1;i<len2;i++){
		cvp += dp2[i];
	}

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

	int t=1;
	// cin >> t;
	while (t--) solve();
 	
	return 0;
}	

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