Submission #964070

#	Time	Username	Problem	Language	Result	Execution time	Memory
964070		pcc	Palindrome-Free Numbers (BOI13_numbers)	C++17	90 / 100	1 ms	600 KiB

numbers

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


ll onepref(ll k){
	if(!k)return 1;
	ll re = 9;
	k--;
	while(k--)re *= 8;
	return re;
}
ll twopref(ll k){
	if(!k)return 1;
	ll re = 1;
	while(k--)re *= 8;
	return re;
}
ll allzero(ll k){
	ll re = 0;
	ll tmp = 1;
	if(!k)return 0;
	else if(k == 1)return 10;
	else if(k == 2)return 91;
	tmp = 9*9;
	k-= 2;
	re = 91;
	while(k--){
		tmp *= 8;
		re += tmp;
	}
	return re;
}

ll f(ll k){
	if(k <= 0)return 0;
	string s = to_string(k);
	int b = s.size();
	ll re = allzero(b-1);
	re += onepref(b-1)*(s[0]-'0'-1);
	for(int i = 1;i<b;i++){
		for(int j = 0;j<s[i]-'0';j++){
			if(j != s[i-1]-'0'&&(i-2<0||j != s[i-2]-'0'))re += twopref(b-1-i);
		}
		if((i-1>=0&&s[i] == s[i-1])||(i-2>=0&&s[i] == s[i-2])){
			break;
		}
	}
	return re;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll a,b;
	cin>>a>>b;
	//cout<<b+1<<":"<<f(b+1)<<' '<<a<<":"<<f(a)<<endl;
	if(!a)cout<<f(b+1);
	else cout<<f(b+1)-f(a);
}

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