Submission #57378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
57378	2018-07-14T17:26:30 Z	RezwanArefin01	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	4 ms	704 KB

numbers

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

typedef long long ll;
typedef pair<int, int> ii; 

ll dp[20][11][11][2][2]; 
string s; 

ll f(int pos, int a, int b, bool small, bool start) {
	if(pos == s.size()) return 1; 
	ll &ret = dp[pos][a][b][small][start]; 
	if(~ret) return ret; 
	ret = 0; 
	int lim = small ? 9 : s[pos] - '0'; 
	for(int i = 0; i <= lim; i++) {
		if(i == a || i == b) continue; 
		if(!i && start) {
			ret += f(pos + 1, 10, 10, 1, 1); 
		} else {
			ret += f(pos + 1, b, i, small | (i < lim), 0); 
		}
	} return ret; 
}

ll solve(ll n) {
    s = to_string(n); 
    memset(dp, -1, sizeof dp); 
    return f(0, 10, 10, 0, 1); 
}

int main(int argc, char const *argv[]) {
    ll a, b; 
    scanf("%lld %lld", &a, &b); 
    ll ans = solve(b); 
    if(a) ans -= solve(a - 1); 
    printf("%lld\n", ans); 
}

Compilation message

numbers.cpp: In function 'll f(int, int, int, bool, bool)':
numbers.cpp:11:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(pos == s.size()) return 1; 
     ~~~~^~~~~~~~~~~
numbers.cpp: In function 'int main(int, const char**)':
numbers.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &a, &b); 
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	520 KB	Output is correct
4	Correct	3 ms	596 KB	Output is correct
5	Correct	2 ms	624 KB	Output is correct
6	Correct	2 ms	624 KB	Output is correct
7	Correct	2 ms	624 KB	Output is correct
8	Correct	3 ms	624 KB	Output is correct
9	Correct	2 ms	624 KB	Output is correct
10	Correct	4 ms	624 KB	Output is correct
11	Correct	3 ms	624 KB	Output is correct
12	Correct	2 ms	636 KB	Output is correct
13	Correct	3 ms	636 KB	Output is correct
14	Correct	3 ms	636 KB	Output is correct
15	Correct	2 ms	636 KB	Output is correct
16	Correct	2 ms	636 KB	Output is correct
17	Correct	3 ms	636 KB	Output is correct
18	Correct	2 ms	636 KB	Output is correct
19	Correct	3 ms	636 KB	Output is correct
20	Correct	2 ms	636 KB	Output is correct

Subtask #2

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	636 KB	Output is correct
2	Correct	3 ms	700 KB	Output is correct
3	Correct	3 ms	700 KB	Output is correct
4	Correct	3 ms	700 KB	Output is correct
5	Correct	3 ms	700 KB	Output is correct
6	Correct	2 ms	700 KB	Output is correct
7	Correct	3 ms	700 KB	Output is correct
8	Correct	3 ms	700 KB	Output is correct
9	Correct	2 ms	700 KB	Output is correct
10	Correct	2 ms	700 KB	Output is correct
11	Correct	2 ms	700 KB	Output is correct
12	Correct	3 ms	700 KB	Output is correct
13	Correct	3 ms	700 KB	Output is correct
14	Correct	2 ms	700 KB	Output is correct
15	Correct	2 ms	700 KB	Output is correct
16	Correct	3 ms	700 KB	Output is correct
17	Correct	4 ms	700 KB	Output is correct
18	Correct	2 ms	700 KB	Output is correct
19	Correct	3 ms	700 KB	Output is correct
20	Correct	3 ms	700 KB	Output is correct
21	Correct	3 ms	700 KB	Output is correct
22	Correct	3 ms	700 KB	Output is correct
23	Correct	3 ms	700 KB	Output is correct
24	Correct	3 ms	700 KB	Output is correct
25	Correct	3 ms	700 KB	Output is correct
26	Correct	3 ms	700 KB	Output is correct
27	Correct	3 ms	700 KB	Output is correct
28	Correct	3 ms	700 KB	Output is correct
29	Correct	3 ms	700 KB	Output is correct
30	Correct	3 ms	700 KB	Output is correct
31	Correct	3 ms	704 KB	Output is correct
32	Correct	2 ms	704 KB	Output is correct
33	Correct	2 ms	704 KB	Output is correct
34	Correct	3 ms	704 KB	Output is correct
35	Correct	3 ms	704 KB	Output is correct
36	Correct	3 ms	704 KB	Output is correct
37	Correct	3 ms	704 KB	Output is correct
38	Correct	3 ms	704 KB	Output is correct
39	Correct	3 ms	704 KB	Output is correct
40	Correct	3 ms	704 KB	Output is correct
41	Correct	4 ms	704 KB	Output is correct
42	Correct	3 ms	704 KB	Output is correct
43	Correct	2 ms	704 KB	Output is correct
44	Correct	3 ms	704 KB	Output is correct
45	Correct	3 ms	704 KB	Output is correct