Submission #779730

#	Time	Username	Problem	Language	Result	Execution time	Memory
779730		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++17	71.25 / 100	1 ms	596 KiB

numbers

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
//#pragma expected_value
//#pragma isolated_call
//#pragma disjoint

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;
using namespace std;

#define int long long
//#define double long double
#define Fi first
#define Se second
#define Rep(i,a,b) for (int i=a;i<=b;++i)
#define Repu(i,b,a) for (int i=b;i>=a;--i)
#define pb push_back
#define ms(a,i) memset(a,i,sizeof(a))
#define sz size()
#define mp make_pair
#define endl '\n'
#define sef setprecision(6)<<fixed
#define cer cout<<"cak"<<endl;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<double> va;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<va> vva;

//const double EPS=1e-9;
const double PI=acos(-1);
const long long oo=1e18;
const int MN=2e5+5;
const int mod=1e9+7;

using cd=complex<double>;

//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> index_set;

int l,r;

string chuyenhoa(int x) {
	string s="";
	while(x>0) {
		s = char(x%10+'0') + s;
		x/=10;
	}
	s='0'+s;
	return s;
}

int dp[25][10][10][10][2];

int solve(string s) {
	Rep(i,0,s.sz-1) Rep(j,0,9) Rep(k,0,9) Rep(t,0,9) dp[i][j][k][t][0] = dp[i][j][k][t][1] = 0;

	dp[0][0][0][0][1] = 1;

	Rep(i,1,1) Rep(p1,0,9) Rep(p2,0,9) 
	{
		Rep(digit,0,9)
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][0];
		}

		Rep(chon,0,9) dp[i][s[i]-'0'][p1][p2][1] += dp[i-1][p1][p2][chon][1];

		Rep(digit,0,9) if(digit < s[i]-'0')
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][1];
		}
	}

	Rep(i,2,2) Rep(p1,0,9) Rep(p2,0,9) 
	{
		Rep(digit,0,9) if(digit!=p1)
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][0];
		}

		if(s[i]-'0' != p1) {
			Rep(chon,0,9) dp[i][s[i]-'0'][p1][p2][1] += dp[i-1][p1][p2][chon][1];
		}

		Rep(digit,0,9) if(digit!=p1 and digit < s[i]-'0')
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][1];
		}
	}


	Rep(i,3,s.sz-1) Rep(p1,0,9) Rep(p2,0,9) 
	{
		Rep(digit,0,9) if(digit!=p1 and digit!=p2)
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][0];
		}

		if(s[i]-'0' != p1 and s[i]-'0' != p2) {
			Rep(chon,0,9) dp[i][s[i]-'0'][p1][p2][1] += dp[i-1][p1][p2][chon][1];
		}

		Rep(digit,0,9) if(digit!=p1 and digit!=p2 and digit < s[i]-'0')
		{
			Rep(chon,0,9) dp[i][digit][p1][p2][0] += dp[i-1][p1][p2][chon][1];
		}
	}

	int ans = 0;
	Rep(p1,0,9) Rep(p2,0,9) Rep(p3,0,9) if(p1!=p2 and p1!=p3)
	{
		ans += dp[s.sz-1][p1][p2][p3][0] + dp[s.sz-1][p1][p2][p3][1];
	}

	return ans;
}

signed main() {
  	//freopen(".inp","r",stdin); freopen(".out","w",stdout);
  	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin>>l>>r;
	if(l==0 and r==0) {
		cout<<1;
		return 0;
	}
	if(r<=9) {
		cout<<r-l+1;
		return 0;
	}
	if(l==0) {
		cout<<solve(chuyenhoa(r))+1;
		return 0;
	}
	cout<<solve(chuyenhoa(r))-solve(chuyenhoa(l-1));
}

Compilation message (stderr)

numbers.cpp: In function 'long long int solve(std::string)':
numbers.cpp:18:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define Rep(i,a,b) for (int i=a;i<=b;++i)
......
   60 |  Rep(i,0,s.sz-1) Rep(j,0,9) Rep(k,0,9) Rep(t,0,9) dp[i][j][k][t][0] = dp[i][j][k][t][1] = 0;
      |      ~~~~~~~~~~                   
numbers.cpp:60:2: note: in expansion of macro 'Rep'
   60 |  Rep(i,0,s.sz-1) Rep(j,0,9) Rep(k,0,9) Rep(t,0,9) dp[i][j][k][t][0] = dp[i][j][k][t][1] = 0;
      |  ^~~
numbers.cpp:18:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define Rep(i,a,b) for (int i=a;i<=b;++i)
......
   97 |  Rep(i,3,s.sz-1) Rep(p1,0,9) Rep(p2,0,9)
      |      ~~~~~~~~~~                   
numbers.cpp:97:2: note: in expansion of macro 'Rep'
   97 |  Rep(i,3,s.sz-1) Rep(p1,0,9) Rep(p2,0,9)
      |  ^~~

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