제출 #1027913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1027913		nghiaaa	Palindrome-Free Numbers (BOI13_numbers)	C++14	83.75 / 100	2 ms	604 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];
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[i][strict][t1 + 1][t2 + 1][dx])
            return dp[i][strict][t1 + 1][t2 + 1][dx];
        ready[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[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));
    return f();
}
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: 23.75 / 25
• Subtask 2: 60 / 75