oj.uz

Submission #57376

# Submission time Handle Problem Language Result Execution time Memory
57376 2018-07-14T16:51:33 Z RezwanArefin01 Palindrome-Free Numbers (BOI13_numbers) C++17
42.5 / 100
 6 ms 1252 KB 
#include <bits/stdc++.h>
using namespace std;

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

ll dp[20][11][11][2][2]; 
char s[20]; 
int len; 

ll f(int pos, int a, int b, bool small, bool start) {
	if(pos == len) 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(int n) {
    sprintf(s, "%lld", n); 
    len = strlen(s); 
    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:23:38: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
    ret += f(pos + 1, b, i, small | i < lim, 0); 
                                    ~~^~~~~
numbers.cpp: In function 'll solve(int)':
numbers.cpp:29:25: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
     sprintf(s, "%lld", n); 
                         ^
numbers.cpp: In function 'int main(int, const char**)':
numbers.cpp:37: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
22.5 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 628 KB Output is correct
3 Incorrect 3 ms 740 KB Output isn't correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 3 ms 900 KB Output is correct
6 Correct 3 ms 900 KB Output is correct
7 Correct 3 ms 900 KB Output is correct
8 Correct 4 ms 900 KB Output is correct
9 Correct 3 ms 900 KB Output is correct
10 Correct 3 ms 900 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 3 ms 900 KB Output is correct
13 Correct 4 ms 900 KB Output is correct
14 Correct 2 ms 900 KB Output is correct
15 Correct 3 ms 900 KB Output is correct
16 Correct 3 ms 900 KB Output is correct
17 Correct 3 ms 900 KB Output is correct
18 Correct 3 ms 916 KB Output is correct
19 Incorrect 3 ms 1048 KB Output isn't correct
20 Correct 3 ms 1048 KB Output is correct

Subtask #2
20.0 / 75.0

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