Submission #77196

# Submission time Handle Problem Language Result Execution time Memory
77196 2018-09-24T01:15:18 Z DrumpfTheGodEmperor Palindrome-Free Numbers (BOI13_numbers) C++14
72.5 / 100
3 ms 740 KB
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1061109567
#define int long long
#define __builtin_popcount __builtin_popcountll
#define pb push_back
#define in(s) freopen(s,"r",stdin);
#define out(s) freopen(s,"w",stdout);
#define fi first
#define se second
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
#define fa(i,x) for (auto i:x)
using namespace std;
int a, b, dig[19], dp[19][11][11];
int solve(int i, int j, int k, bool flag) {
	if (!i) return 1;
	if (dp[i][j][k] != -1 && !flag) return dp[i][j][k];
	int n = (flag ? dig[i] : 9), ans = 0;
	fw (nxt, 0, n + 1) if (nxt != j && nxt != k) {
		ans += solve(i - 1, nxt, j, flag && nxt == n ? 1 : 0);
	}
	if (!flag) dp[i][j][k] = ans;
	return ans;
}
int calc(int r) {
	if (r == -1) return 0;
	int cnt = 0;
	while (r) {
		dig[++cnt] = r % 10;
		r /= 10;
	}
	return solve(cnt, 10, 10, 1);
}
signed main() {
	#ifdef aome
	in("aome.inp");	
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> a >> b;
	memset(dp, -1, sizeof dp);
	cout << calc(b) - calc(a - 1) << "\n";
	return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 448 KB Output isn't correct
3 Correct 2 ms 448 KB Output is correct
4 Incorrect 2 ms 544 KB Output isn't correct
5 Incorrect 2 ms 544 KB Output isn't correct
6 Incorrect 2 ms 544 KB Output isn't correct
7 Incorrect 2 ms 592 KB Output isn't correct
8 Incorrect 2 ms 592 KB Output isn't correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Incorrect 2 ms 592 KB Output isn't correct
15 Incorrect 2 ms 592 KB Output isn't correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 2 ms 624 KB Output is correct
19 Correct 2 ms 624 KB Output is correct
20 Incorrect 2 ms 624 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct
2 Correct 2 ms 624 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Incorrect 2 ms 688 KB Output isn't correct
6 Correct 2 ms 688 KB Output is correct
7 Incorrect 2 ms 688 KB Output isn't correct
8 Incorrect 2 ms 688 KB Output isn't correct
9 Incorrect 2 ms 688 KB Output isn't correct
10 Incorrect 2 ms 688 KB Output isn't correct
11 Correct 2 ms 688 KB Output is correct
12 Incorrect 2 ms 688 KB Output isn't correct
13 Incorrect 3 ms 688 KB Output isn't correct
14 Incorrect 2 ms 688 KB Output isn't correct
15 Incorrect 2 ms 688 KB Output isn't correct
16 Correct 2 ms 688 KB Output is correct
17 Correct 2 ms 688 KB Output is correct
18 Correct 3 ms 688 KB Output is correct
19 Correct 3 ms 688 KB Output is correct
20 Correct 3 ms 688 KB Output is correct
21 Correct 2 ms 688 KB Output is correct
22 Correct 2 ms 688 KB Output is correct
23 Correct 2 ms 688 KB Output is correct
24 Correct 2 ms 688 KB Output is correct
25 Correct 2 ms 688 KB Output is correct
26 Correct 2 ms 688 KB Output is correct
27 Correct 2 ms 688 KB Output is correct
28 Correct 2 ms 688 KB Output is correct
29 Correct 2 ms 688 KB Output is correct
30 Correct 2 ms 688 KB Output is correct
31 Correct 2 ms 688 KB Output is correct
32 Correct 2 ms 688 KB Output is correct
33 Correct 2 ms 688 KB Output is correct
34 Correct 2 ms 688 KB Output is correct
35 Correct 2 ms 688 KB Output is correct
36 Correct 2 ms 688 KB Output is correct
37 Correct 2 ms 688 KB Output is correct
38 Correct 2 ms 688 KB Output is correct
39 Correct 2 ms 688 KB Output is correct
40 Correct 2 ms 688 KB Output is correct
41 Correct 2 ms 740 KB Output is correct
42 Correct 3 ms 740 KB Output is correct
43 Correct 2 ms 740 KB Output is correct
44 Correct 2 ms 740 KB Output is correct
45 Correct 2 ms 740 KB Output is correct