Submission #939105

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
939105	2024-03-06T05:45:13 Z	tamir1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	600 KB

numbers

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,dp[20][2][2][2];
vector<ll> v;
void build(ll a){
	if(a<10){
		v.push_back(a);
		return;
	}
	build(a/10);
	v.push_back(a%10);
}
ll rec(ll idx,ll t,ll s,ll u,ll last1,ll last2){
	if(idx==v.size()) return 1;
	if(dp[idx][t][s][u]!=-1) return dp[idx][t][s][u];
	ll i,up=9,ans=0;
	if(!t) up=v[idx];
	for(i=0;i<=up;i++){
		if(s && last2==i) continue;
		if(u && last1==i) continue;
		ans+=rec(idx+1,t|(i<up),s|(i>0),u|s,last2,i);
	}
	return dp[idx][t][s][u]=ans;
}
ll solve(ll a){
	if(a==-1) return 0;
	v.clear();
	build(a);
	memset(dp,-1,sizeof dp);
	return rec(0,0,0,0,0,0);
}
int main(){
	cin >> a >> b;
	cout << solve(b)-solve(a-1);
}

Compilation message

numbers.cpp: In function 'long long int rec(long long int, long long int, long long int, long long int, long long int, long long int)':
numbers.cpp:15:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(idx==v.size()) return 1;
      |     ~~~^~~~~~~~~~

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 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	0 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	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 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	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 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	0 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	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 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	348 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	436 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	372 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 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	348 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 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	348 KB	Output is correct
41	Correct	0 ms	344 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	0 ms	348 KB	Output is correct