Submission #676499

#	Time	Username	Problem	Language	Result	Execution time	Memory
676499		penguin133	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	3 ms	340 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 5e8 + 1;
int dp[20][10][10][2];
int x,y, tmp,cnt;
vector<int>v;
int calc(int i, int sec, int lst, int con){
	if(i >= (int)v.size())return 1;
	if(dp[i][sec][lst][con]>0)return dp[i][sec][lst][con];
	if(con){
		int ans =0;
		if(i && lst && sec && v[i])ans += calc(i+1, lst,0 ,0);
		for(int j=1;j<v[i];j++)if(j != lst && j != sec)ans += calc(i+1, lst, j, 0);
		if(v[i] != lst && v[i] != sec)ans += calc(i+1, lst, v[i], 1);
		//cout << i << " " << sec << " " << lst <<  " " << con << " " << ans << '\n';
		return dp[i][sec][lst][con]= ans;
	}
	else{
		int ans =0;
		if(i && sec && lst)ans += calc(i+1, lst, 0, 0);
		for(int j=1;j<=9;j++)if(j != lst && j != sec)ans += calc(i+1, lst, j, 0);
		return dp[i][sec][lst][con] = ans;
	}
}
main(){
	//ios::sync_with_stdio(0);cin.tie(0);
	cin >> x >> y;
	if(y == 0)return cout << 1, 0;
	tmp = y;
	cnt =0;
	int tmp2 = y;
	while(tmp2)v.push_back(tmp2%10), tmp2 /= 10;
	reverse(v.begin(), v.end());
	memset(dp, -1, sizeof(dp));
	int ans1 = calc(0, 10, 10, 1);
	//cout << ans1 << '\n';
	v.pop_back();
	while(v.size()){
		memset(dp, -1, sizeof(dp));
		ans1 += calc(0, 10, 10, 0);
		//cout << ans1 << '\n';
		v.pop_back();
	}
	//cout << ans1 << '\n';
	if(x == 0)return cout << ans1+1, 0;
	else if(x == 1)return cout << ans1, 0;
	tmp = --x;
	v.clear();
	memset(dp,-1, sizeof(dp));
	while(tmp > 0)v.push_back(tmp%10), tmp/=10;
	reverse(v.begin(), v.end());
	int ans2 = calc(0, 10, 10, 1);
	v.pop_back();
	while(v.size()){
		memset(dp, -1, sizeof(dp));
		ans2 += calc(0, 10, 10, 0);
		v.pop_back();
	}
	cout << ans1 - ans2 << '\n';
	
}

Compilation message (stderr)

numbers.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~

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