Submission #888404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888404	2023-12-17T09:49:17 Z	vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	600 KB

numbers

#include "bits/stdc++.h"
using namespace std;
bool START;
void init();
void solve();
bool multitest();
void time_and_memory();
clock_t TIME = clock();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int TEST = 1;
    if (multitest()) cin >> TEST;
    while (TEST--) solve();
    time_and_memory();
}

bool multitest() {
    return 0;
}

void init() {
}

#define int long long

int n, digit[19], dp[19][11][11][2][2];

int DP(int p, int num0, int num1, bool s, bool ok) {
    if (p == n) return ok;
    if (dp[p][num0+1][num1+1][s][ok] != -1)
        return dp[p][num0+1][num1+1][s][ok];

    int loop = max(digit[p], 9LL * s), res = 0;

    for (int i = 0; i <= loop; ++i)
        if (num1 == -1 && i == 0)
            res += DP(p+1, -1, -1, 1, 0);
        else if (i == num0 || i == num1)
            res += DP(p+1, num1, i, s | (i < loop), 1);
        else
            res += DP(p+1, num1, i, s | (i < loop), ok);

    return dp[p][num0+1][num1+1][s][ok] = res;
}

int ac(int x) {
    if (x < 0) return 0;

    n = 0;
    for (; x > 0; x /= 10) digit[n++] = x % 10;
    reverse(digit, digit+n);

    memset(dp, -1, sizeof(dp));

    return DP(0, -1, -1, 0, 0);
}

void solve() {
    int a, b;
    cin >> a >> b;
    cout << (b - a + 1) - (ac(b) - ac(a - 1));
}

bool END;
void time_and_memory() {
    cerr << "\nUsed: " << clock() - TIME << " ms, ";
    cerr << fixed << setprecision(3);
    cerr << fabs((&START - &END) / 1048576.0) << " MB\n\n";
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	460 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	600 KB	Output is correct

Subtask #2

75.0 / 75.0

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