Submission #102369

#	Time	Username	Problem	Language	Result	Execution time	Memory
102369		groeneprof	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	3 ms	512 KiB

numbers

#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;

int f(string a){
	//cout<<"------------------------ "<<a<<endl;
	int memo[a.size()+1][11][11][2];
	F(i, a.size()+1) F(j, 11) F(k, 11) F(l, 2){
		memo[i][j][k][l] = 0;
	}
	memo[0][10][10][0] = 1;
	FR(i, 1, a.size()+1){
		F(j, 11){
			F(k, 11){
				F(l, 2){
					F(m, 10) if(m!=j&&m!=k && (l==1||m+'0'<=a[i-1]) && (k!=10 || m!= 0)){
						memo[i][k][m][(int)(l==1||m+'0'<a[i-1])] += memo[i-1][j][k][l];
					}
					if(k == 10 && l == 1){
						memo[i][k][10][1]+=memo[i-1][j][k][0]+memo[i-1][j][k][1];
					}
				}
			}
		}
	}
	int res = 0;
	F(j, 11) F(k,11) F(l, 2){
		P(j<<" "<<k<<" "<<l<<": "<<memo[a.size()][j][k][l]);
		res+=memo[a.size()][j][k][l];
	}
	return res;
}

signed main() {
	ios_base::sync_with_stdio(true);
	cin.tie(0);
	int a, b;
	cin>>a>>b;
	if(b==0) cout<<1;
	else if(a==0) cout<<f(to_string(b));
	else cout<<f(to_string(b))-f(to_string(a-1));
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int f(std::__cxx11::string)':
numbers.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FR(i, a, b) for(int i = (a); i < (b); ++i)
                                        ^
numbers.cpp:6:17: note: in expansion of macro 'FR'
 #define F(i, n) FR(i, 0, n)
                 ^~
numbers.cpp:22:2: note: in expansion of macro 'F'
  F(i, a.size()+1) F(j, 11) F(k, 11) F(l, 2){
  ^
numbers.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FR(i, a, b) for(int i = (a); i < (b); ++i)
                                        ^
numbers.cpp:26:2: note: in expansion of macro 'FR'
  FR(i, 1, a.size()+1){
  ^~

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