Submission #964077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964077	2024-04-16T09:37:23 Z	pcc	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	604 KB

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

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	604 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	452 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #2

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	456 KB	Output is correct
16	Correct	0 ms	352 KB	Output is correct
17	Correct	0 ms	356 KB	Output is correct
18	Correct	1 ms	356 KB	Output is correct
19	Correct	0 ms	352 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	456 KB	Output is correct
22	Correct	1 ms	452 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	344 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	460 KB	Output is correct
32	Correct	1 ms	348 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	1 ms	456 KB	Output is correct
36	Correct	1 ms	344 KB	Output is correct
37	Correct	0 ms	456 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	0 ms	352 KB	Output is correct
41	Correct	0 ms	348 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	456 KB	Output is correct
44	Correct	0 ms	344 KB	Output is correct
45	Correct	0 ms	348 KB	Output is correct