Submission #69863

# Submission time Handle Problem Language Result Execution time Memory
69863 2018-08-21T17:18:31 Z MatheusLealV Palindrome-Free Numbers (BOI13_numbers) C++17
96.25 / 100
6 ms 872 KB
#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(b == 0) R --;

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

Compilation message

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++)
                 ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 408 KB Output is correct
3 Correct 4 ms 428 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Incorrect 2 ms 552 KB Output isn't correct
6 Incorrect 3 ms 564 KB Output isn't correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 3 ms 572 KB Output is correct
10 Correct 2 ms 572 KB Output is correct
11 Correct 2 ms 584 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 720 KB Output is correct
15 Incorrect 3 ms 720 KB Output isn't correct
16 Correct 4 ms 720 KB Output is correct
17 Correct 3 ms 720 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 4 ms 720 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 720 KB Output is correct
2 Correct 5 ms 720 KB Output is correct
3 Correct 4 ms 720 KB Output is correct
4 Correct 4 ms 720 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 720 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 728 KB Output is correct
9 Correct 2 ms 736 KB Output is correct
10 Correct 3 ms 736 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 3 ms 752 KB Output is correct
15 Correct 3 ms 756 KB Output is correct
16 Correct 4 ms 760 KB Output is correct
17 Correct 5 ms 760 KB Output is correct
18 Correct 4 ms 768 KB Output is correct
19 Correct 5 ms 772 KB Output is correct
20 Correct 4 ms 776 KB Output is correct
21 Correct 4 ms 776 KB Output is correct
22 Correct 3 ms 776 KB Output is correct
23 Correct 4 ms 788 KB Output is correct
24 Correct 5 ms 792 KB Output is correct
25 Correct 4 ms 796 KB Output is correct
26 Correct 5 ms 800 KB Output is correct
27 Correct 5 ms 804 KB Output is correct
28 Correct 5 ms 860 KB Output is correct
29 Correct 5 ms 860 KB Output is correct
30 Correct 4 ms 860 KB Output is correct
31 Correct 4 ms 860 KB Output is correct
32 Correct 5 ms 860 KB Output is correct
33 Correct 4 ms 860 KB Output is correct
34 Correct 5 ms 860 KB Output is correct
35 Correct 6 ms 860 KB Output is correct
36 Correct 5 ms 860 KB Output is correct
37 Correct 5 ms 860 KB Output is correct
38 Correct 4 ms 860 KB Output is correct
39 Correct 4 ms 860 KB Output is correct
40 Correct 5 ms 860 KB Output is correct
41 Correct 6 ms 860 KB Output is correct
42 Correct 5 ms 864 KB Output is correct
43 Correct 4 ms 868 KB Output is correct
44 Correct 5 ms 872 KB Output is correct
45 Correct 4 ms 872 KB Output is correct