Submission #736223

#	Time	Username	Problem	Language	Result	Execution time	Memory
736223		sleepntsheep	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	420 KiB

numbers

/*
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 (stderr)

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 / 25
• Subtask 2: 75 / 75