Submission #1255215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255215		EkinOnal	Palindrome-Free Numbers (BOI13_numbers)	C++20	76.25 / 100	1095 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),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(kalan==1) {return to_go.size();} // burasi sikintili gibi

	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/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);
	}
//	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; pre[0]=1; pre[1]=9+pre[0]; pre[2]=pre[1]+81;
	for(int i=3;i<=18;i++) dp[i]=dp[i-1]*8, dp2[i]=dp2[i-1]*8, pre[i]=pre[i-1]+dp2[i];


	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;

	int cvp=f(len2,b,-1,-1,1)+pre[len2-1]-f(len1,a,-1,-1,1)-pre[len1-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<=19;i++) uson[i]=uson[i-1]*10;

// 	int sayac=0;
// 	for(int i=100;i<=321;i++){
// 		vi v; int j=i;
// 		while(j) v.pb(j%10), j/=10;
// 		reverse(v.begin(),v.end());

// 		if(v.size()==3){
// 			if(v[0]!=v[1] && v[1]!=v[2] && v[0]!=v[2]) sayac++;
// 		}
// 		else if(v.size()==2 && v[0]!=v[1]) sayac++;
// 		else sayac++;
// 	}	
// //	cout<<sayac<<"\n";

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

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