제출 #1255239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255239		EkinOnal	Palindrome-Free Numbers (BOI13_numbers)	C++20	93.75 / 100	0 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 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(kalan==1) {return (int)to_go.size();} // burasi sikintili gibi

	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;
	}

	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<=17;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: 18.75 / 25
• Subtask 2: 75 / 75