oj.uz

Submission #736223

# Submission time Handle Problem Language Result Execution time Memory
736223 2023-05-05T10:35:40 Z sleepntsheep Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 420 KB 
/*
TASK: 6mar_palindromefree
LANG: C
*/
#include <stdio.h>
#include <string.h>

typedef long long s64;

/* pos, second last char, last char, is palindrome, less than flag, in leading zero */
s64 dp[20][11][11][2][2][2], a, b;
char s[20];

s64 rcs(int pos, int l2, int l1, int pal, int f2, int lz)
{
    s64 &d = dp[pos][l2][l1][pal][f2][lz];
    if (-1 != d) return d;
    if (!s[pos]) return d = pal;
    d = 0;
    for (int i = 0; i <= (f2 ? 9 : s[pos] - '0'); ++i)
    {
        int nlz = lz ? !i : 0;
        int nl2 = nlz ? 10 : l1, nl1 = nlz ? 10 : i;
        d += rcs(pos+1, nl2, nl1, pal || (!lz && (l1 == i || l2 == i)), f2 || (i < s[pos] - '0'), nlz);
    }
    return d;
}

s64 solve(s64 num)
{
    memset(dp, -1, sizeof dp);
    snprintf(s, sizeof s, "%018lld", num);
    return rcs(0, 10, 10, 0, 0, 1);
}

int main()
{
    scanf("%lld%lld", &a, &b);
    printf("%lld\n", (b - a + 1) - (solve(b) - solve(a-1)));
    return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld%lld", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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