Submission #370316

#	Time	Username	Problem	Language	Result	Execution time	Memory
370316		knightron0	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	14 ms	15596 KiB

numbers

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e5 + 5;

vector<int> v1, v2;
int dp1[20][22][22][2][2][25], dp2[20][22][22][2][2][25];

int solve1(int idx, int p1, int p2, bool same_upper, bool all_zeroes, int start){
	if(idx == (int)v1.size()) return 1;
	int hi = v1[idx];
	int ans= 0;
	if(dp1[idx][p1+1][p2+1][same_upper][all_zeroes][start] != -1) return dp1[idx][p1+1][p2+1][same_upper][all_zeroes][start];
	for(int i= 0;i<10;i++){
		bool valid = true;
		if(same_upper){
			if(i > hi) valid = false;
		}
		if((i == p1) && start < idx) {
			valid = false;
		}
		if((i == p2) && start < idx-1){
			valid = false;
		}
		if(!valid) continue;
		bool newb = (hi == i) && same_upper;
		bool same_zeroes = (i == 0) && all_zeroes;
		int newstart = start;
		if(all_zeroes && (i != 0)){
			newstart = idx;
		}
		ans += solve1(idx+1, i, p1, newb, same_zeroes, newstart);
	}
	return dp1[idx][p1+1][p2+1][same_upper][all_zeroes][start] = ans;
}

int solve2(int idx, int p1, int p2, bool same_upper, bool all_zeroes, int start){
	if(idx == (int)v2.size()) return 1;
	int hi = v2[idx];
	int ans= 0;
	if(dp2[idx][p1+1][p2+1][same_upper][all_zeroes][start] != -1){
		return dp2[idx][p1+1][p2+1][same_upper][all_zeroes][start];
	}
	for(int i= 0;i<10;i++){
		bool valid = true;
		if(same_upper){
			if(i > hi) valid = false;
		}
		if((i == p1) && start < idx) {
			valid = false;
		}
		if((i == p2) && start < idx-1){
			valid = false;
		}
		if(!valid) continue;
		bool newb = (hi == i) && same_upper;
		bool same_zeroes = (i == 0) && all_zeroes;
		int newstart = start;
		if(all_zeroes && (i != 0)){
			newstart = idx;
		}
		ans += solve2(idx+1, i, p1, newb, same_zeroes, newstart);
	}
	return dp2[idx][p1+1][p2+1][same_upper][all_zeroes][start] = ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    int x, y;
    cin>>x>>y;
    int num = 0;
    if(x == 0){
    	num = 1;
    }
    x = max(x-1, 0LL);
    while(x>0){
    	v1.pb(x%10);
    	x/=10;
    }
    while(y>0){
    	v2.pb(y%10);
    	y/=10;
    }
    reverse(all(v1));
    reverse(all(v2));
    clr(dp1, -1);
    clr(dp2, -1);
    cout<<solve2(0, -1, -1, 1, 1, 20)-solve1(0, -1, -1, 1, 1, 20)+num<<endl;
    return 0;
}

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