Submission #527542

#	Time	Username	Problem	Language	Result	Execution time	Memory
527542		jalsol	Palindrome-Free Numbers (BOI13_numbers)	C++11	100 / 100	1 ms	332 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 5e5 + 5;

string a, b;
ll dp[20][2][2][11][11];

ll go(int p, bool lo, bool hi, int last, int prelast, bool sig) {
    if (p >= isz(a)) return 1;

    ll& ret = dp[p][lo][hi][last][prelast];
    if (ret != -1) return ret;

    ret = 0;
    int l = 0, r = 9;
    if (lo) l = a[p] - '0';
    if (hi) r = b[p] - '0';

    For (d, l, r) {
        bool nxtLo = lo && (d == l);
        bool nxtHi = hi && (d == r);

        if (!sig && d == 0) {
            ret += go(p + 1, nxtLo, nxtHi, last, prelast, sig);
        } else if (d != last && d != prelast) {
            ret += go(p + 1, nxtLo, nxtHi, d, last, true);
        }
    }

    return ret;
}

signed main() {
    cin >> a >> b;
    while (isz(a) < isz(b)) a = '0' + a;
    while (isz(a) > isz(b)) b = '0' + b;

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

    cout << go(0, true, true, 10, 10, false);
}

/*

*/

Compilation message (stderr)

numbers.cpp: In constructor '__Init__::__Init__()':
numbers.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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