Submission #1238692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238692		chikien2009	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	724 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int d[20], len;
long long f[20][20][100], a, b;

inline long long Form(int ind, int non_space, int cur, bool limit, long long num)
{
    if (ind == -1)
    {
        // cout << non_space << " " << num << " " << cur << "\n";
        return 1;
    }
    if (f[ind][non_space][cur] != -1 && !limit)
    {
        return f[ind][non_space][cur];
    }
    long long res = 0;
    int nxt_non_space, nxt_cur;
    bool nxt_limit;
    for (int i = 0; i <= (limit ? d[ind] : 9); ++i)
    {
        if ((non_space == 0 || cur % 10 != i) &&
            (non_space <= 1 || cur / 10 != i))
        {
            nxt_non_space = non_space + (non_space > 0 || i > 0);
            nxt_cur = (cur % 10) * 10 + i;
            nxt_limit = (limit & (i == d[ind]));
            res += Form(ind - 1, nxt_non_space, nxt_cur, nxt_limit, num * 10 + i);
        }
    }
    if (!limit)
    {
        f[ind][non_space][cur] = res;
    }
    return res;
}

inline long long G(long long inp)
{
    len = 0;
    do
    {
        d[len++] = inp % 10;
    } while (inp /= 10);
    for (int i = 0; i < 20; ++i)
    {
        for (int j = 0; j < 100; ++j)
        {
            for (int k = 0; k < 20; ++k)
            {
                f[i][k][j] = -1;
            }
        }
    }
    return Form(len - 1, 0, 0, 1, 0);
}

int main()
{
    setup();

    cin >> a >> b;
    cout << G(b) - G(a - 1);
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75