Submission #647390

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

numbers

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 20;

int cnt_lt_pre(int *msd, int i)
{
	int ans = 0;
	ans += i>0 && msd[i-1] < msd[i];
	ans += i>1 && msd[i-2] < msd[i];
	return ans;
}

bool is_equal(int *msd, int i)
{
	if (i>0 && msd[i] == msd[i-1])
		return 1;
	if (i>1 && msd[i] == msd[i-2])
		return 1;
	return 0;
}

ll cnt_lt_arr(int *msd, int len, int first_lt)
{
	ll ans = 1;
	if (msd == NULL) {
		Loop (i,0,len)
			ans *= i<2? 9: 8;
		return ans;
	}
	Loop (i,0,first_lt) {
		if (is_equal(msd, i))
			return 0;
	}
	ans *= msd[first_lt] - cnt_lt_pre(msd, first_lt) - (first_lt == 0);
	Loop (i,first_lt+1,len)
		ans *= max(8ll, 10-i);
	return ans;
}

pair<int *, int> make_arr(ll x)
{
	int *ans = new int[N];
	int len = 0;
	while (x) {
		ans[len++] = x%10;
		x /= 10;
	}
	reverse(ans, ans+len);
	return {ans, len};
}

ll cnt_lt(ll x)
{
	if (x == 0)
		return 0;
	auto [arr, len] = make_arr(x);
	ll ans = 1 /* 0 is valid too */;
	Loop (i,1,len)
		ans += cnt_lt_arr(NULL, i, 0);
	Loop (i,0,len)
		ans += cnt_lt_arr(arr, len, i);
	delete[](arr);
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	ll l, r;
	cin >> l >> r;
	cout << cnt_lt(r+1) - cnt_lt(l) << '\n';
}

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