Submission #69865

#	Time	Username	Problem	Language	Result	Execution time	Memory
69865		MatheusLealV	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	6 ms	696 KiB

numbers

#include <bits/stdc++.h>
#define N 25
using namespace std;
typedef long long ll;

ll a, b, A[N], B[N], sz[2];

void fill(ll x, ll t)
{
	vector<ll> v;

	while(x > 0)
	{
		ll r = x % 10;

		v.push_back(r);

		x /= 10;
	}

	reverse(v.begin(), v.end());

	sz[t] = v.size();

	for(int i = 0; i < v.size(); i++)
		if(!t) A[i+1] = v[i];
		else B[i+1] = v[i];
}

// F = 1, O NUMERO JÁ É ESTRITAMENTE MENOR
//F = 0, O NUMERO É EXATAMENTE IGUAL

ll dp[N][13][13][2];

ll solveA(int i, int a, int b, int f)
{
	if(i > sz[0]) return 1;

	if(dp[i][a+1][b+1][f] != -1) return dp[i][a+1][b+1][f];

	ll ans = 0;

	for(int k = 0; k < 10; k++)
	{
		if((i == 1 and !k) or k == a or k == b) continue;

		if(f == 1) ans += solveA(i + 1, k, a, f);

		else
		{
			if(k < A[i]) ans += solveA(i + 1, k, a, 1);

			else if(k == A[i]) ans += solveA(i + 1, k, a, 0);
		}
	}

	return dp[i][a+1][b+1][f] = ans;
}

int t;

ll solveA2(int i, int a, int b, int f)
{
	if(i > t) return 1;

	if(dp[i][a+1][b+1][f] != -1) return dp[i][a+1][b+1][f];

	ll ans = 0;

	for(int k = 0; k < 10; k++)
	{
		if((i == 1 and !k) or k == a or k == b) continue;

		ans += solveA2(i + 1, k, a, f);
	}

	return dp[i][a+1][b+1][f] = ans;
}

int main()
{
	cin>>a>>b;

	a--;

	fill(a, 0);

	memset(dp, -1, sizeof dp);

	ll L = solveA(1, -1, -1, 0);

	for(int T = 1; T < sz[0]; T++)
	{
		t = T;

		memset(dp, -1, sizeof dp);

		L += solveA2(1, -1, -1, 0);
	}

	memset(dp, -1, sizeof dp);

	fill(b, 0);

	ll R = solveA(1, -1, -1, 0);

	for(int T = 1; T < sz[0]; T++)
	{
		t = T;

		memset(dp, -1, sizeof dp);

		R += solveA2(1, -1, -1, 0);
	}

	if(a < 0) L -= 2;

	if(a == 0) L--;

	if(b == 0) R --;

	cout<<R - L<<"\n";
}

Compilation message (stderr)

numbers.cpp: In function 'void fill(ll, ll)':
numbers.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++)
                 ~~^~~~~~~~~~

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