Submission #1124073

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

numbers

#include <bits/stdc++.h>
#define Y8o "BOI13_numbers"
#define maxn (int) 20
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b) for(int i = a; i <= b; i ++)
#define fid(i, a, b) for(int i = a; i >= b; i --)

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


string A, B;
vector<int> a;
ll dp[20][2][2][12][12];

ll calc(int pos, int st, int small, int pre_pre, int pre) {
    if(pos == (int)a.size()) return 1;
    ll &best = dp[pos][st][small][pre_pre + 1][pre + 1];
    if(best != -1) return best;

    best = 0;
    int lim = small ? 9 : a[pos];

    fi(i, 0, lim) {
        int nw_st = st | (i != 0);
        int nw_small = small | (i < lim);
        if(!nw_st) best += calc(pos + 1, nw_st, nw_small, pre_pre, pre);
        else {
            if(i != pre && i != pre_pre) {
                best += calc(pos + 1, nw_st, nw_small, pre, i);
            }
        }
    }
    return best;
}

ll prog(string& S) {
    a.clear();
    fi(i, 0, S.size() - 1) a.push_back(S[i] - '0');

    memset(dp, -1, sizeof dp);
    return calc(0, 0, 0, -1, -1);
}

int check(string& S) {
    fi(i, 1, S.size() - 1) {
        if(S[i] == S[i - 1]) return 0;
        if(i >= 2 && S[i] == S[i - 2]) return 0;
    }
    return 1;
}

void solve() {
    cin >> A >> B;
    cout << prog(B) - prog(A) + check(A) << '\n';
}


int main() {
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'void iof()':
numbers.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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