Submission #507515

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
507515	2022-01-12T15:47:37 Z	magmag	Palindrome-Free Numbers (BOI13_numbers)	C++17	73.75 / 100	1 ms	332 KB

numbers

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

int len;
string upper;

// len-1, len-2, ... ,0
// 0, 1, ... len-1
ll dp[19][2][10][10];

ll calc(int i = 0, bool touch = 1, int p = -1, int pp = -1) {
    if (i == len)return 1;

    if (dp[i][touch][p][pp] != -1)return dp[i][touch][p][pp];

    ll ret = 0;
    if (touch) {
        int uuu = upper[i] - '0';
        for (int d = 0; d <= uuu; ++d) {
            if (d == p || d == pp)continue;
            ret += calc(i+1, d == uuu, d, p);
        }
    } else {
        for (int d = 0; d < 10; ++d) {
            if (d == p || d == pp)continue;
            ret += calc(i+1, false, d, p);
        }
    }
    return dp[i][touch][p][pp] = ret;
}

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

    memset(dp, -1, sizeof dp);
    upper = to_string(b);
    len = upper.length();

    ll ans = calc();

    if (a > 1) {
        memset(dp, -1, sizeof dp);
        upper = to_string(a-1);
        len = upper.length();
        ans -= calc();
    }

    cout << ans << endl;

    return 0;
}

Subtask #1

13.75 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Incorrect	0 ms	204 KB	Output isn't correct
3	Correct	1 ms	296 KB	Output is correct
4	Incorrect	0 ms	304 KB	Output isn't correct
5	Correct	0 ms	204 KB	Output is correct
6	Incorrect	0 ms	204 KB	Output isn't correct
7	Incorrect	1 ms	204 KB	Output isn't correct
8	Incorrect	0 ms	296 KB	Output isn't correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	300 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	0 ms	296 KB	Output is correct
14	Incorrect	1 ms	332 KB	Output isn't correct
15	Incorrect	0 ms	204 KB	Output isn't correct
16	Correct	0 ms	292 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	1 ms	300 KB	Output is correct
20	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #2

60.0 / 75.0

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