Submission #968071

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

numbers

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int l, r;
vector<int> a;

int dp[19][2][11][11][2];

int F(int pos, bool state, int pre_lst, int lst, bool zero){
    if (pos == (int)a.size()) return 1;
    int &ret = dp[pos][state][pre_lst][lst][zero];
    if(~ret) return ret;
    ret = 0;
    int Lim = (state ? 9 : a[pos]);
    for (int c = 0; c <= Lim; ++c){
        if (c == pre_lst || c == lst) continue;
        bool nxt_state = (state | (c < Lim));
        int nxt_plst = pre_lst, nxt_lst = lst;

        bool nxt_zero = (zero | (c > 0));
        if(nxt_zero){
            nxt_plst = lst;
            nxt_lst = c;
        }
        ret += F(pos + 1, nxt_state, nxt_plst, nxt_lst, nxt_zero);
    }
    return ret;
}
int G(int x){
    a.clear();
    if (x < 0) return 0;
    while (x > 0){
        a.push_back(x % 10); x /= 10;
    }
    reverse(a.begin(), a.end());
    memset(dp, -1, sizeof dp);
    return F(0, 0, 10, 10, 0);
}
void Whisper(){
    cin >> l >> r;
    cout << G(r) - G(l - 1);
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

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