Submission #1027924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027924		nghiaaa	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	1 ms	516 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
const int mod = 998244353;
inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//mt19937 RAND(seed);
inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
inline int mul(int u,int v){return (ll)u*v%mod;}
vector<int> digit;
bool ready[19][2][11][11][2];
ll dp[19][2][11][11][2];
int n;
ll f(int i = 0, bool strict = 1, int t1 = -1, int t2 = -1, bool dx = 0)
{
    if (i == sz(digit))
    {
        if (dx) return 1;
        return 0;
    }
    if (!strict)
    {
        if (ready[n - i][strict][t1 + 1][t2 + 1][dx])
            return dp[n - i][strict][t1 + 1][t2 + 1][dx];
        ready[n - i][strict][t1 + 1][t2 + 1][dx] = 1;
    }
    int E = strict ? digit[i] : 9;
    ll ansf = 0;
    forw(u, 0, E)
    {
        int nxt = u;
        bool ndx = dx, nstrict = strict;
        if (nxt == t1 || nxt == t2)
            ndx = 1;
        if (nxt == 0 && t2 == -1)
            nxt = -1;
        if (nstrict && nxt < E)
            nstrict = 0;
        ansf += f(i + 1, nstrict, t2, nxt, ndx);
    }
    if (!strict)
        dp[n - i][strict][t1 + 1][t2 + 1][dx] = ansf;
    return ansf;
}
ll getr(ll u)
{
    digit.clear();
    if (u == 0) return 0;
    while(u)
    {
        digit.pb(u % 10);
        u /= 10;
    }
    reverse(all(digit));
    n = sz(digit);
    return f();
}
bool ok(ll u)
{
    int t1 = -1 , t2 = -1;
    while(u)
    {
        int val = u % 10;
        u /= 10;
        if (val == t1 || val == t2)
            return 0;
        t1 = t2;
        t2 = val;
    }
    return 1;
}
void solve()
{
    ll a, b;
    cin >> a >> b;
    ll range = getr(b) - getr(a - 1);
    cout << b - a + 1 - range;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.inp","r",stdin);
   // freopen("test.out","w",stdout);
    //time_t TIME_TU=clock();
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

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