oj.uz

Submission #1027924

# Submission time Handle Problem Language Result Execution time Memory
1027924 2024-07-19T11:37:23 Z nghiaaa Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 1 ms 516 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 424 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 516 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct