oj.uz

Submission #383256

# Submission time Handle Problem Language Result Execution time Memory
383256 2021-03-29T11:10:19 Z Sara Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 2 ms 512 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long int
#define F first
#define S second
#define pb push_back

const ll N = 3e5 + 5;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;

ll dp[20][2][10][10];

// 50 -> tool
// 2 -> koochiktar shode?
// 20 -> raghame yeki moonde be akhar
// 20 raghame akhar

int l[20], r[20], tmp[20], a[20];

inline int pre(ll x){
    int cur = -1;
    fill(tmp, tmp + 20, 0);
    for (int i = 18; i >= 1; i --){
        if ((x == 0) && (cur == -1)){
            cur = i;
        }
        tmp[i] = x % 10; 
        x /= 10ll;
    }
    fill(a, a + 20, 0);
    for (int i = 1; cur + i <= 18; i ++){
        a[i] = tmp[cur + i];
    }
    return 18 - cur;
}

inline ll solve(int s, int e){

    if (e - s + 1 == 1){
        return a[1] + 1;
    }

    memset(dp, 0, sizeof dp);

    if (a[1] != a[2]){
        dp[2][0][a[1]][a[2]] ++;
    } 
    s += 2;
    for (int i = 1; i < 10; i ++){
        for (int j = 0; j < 10; j ++){
            if (i == j) continue;
            if (i < a[1] || (i == a[1] && j < a[2])){
                dp[2][1][i][j] ++;
            }
        }
    }

    for (int n = s; n <= e; n ++){
        for (int i = 0; i < 10; i ++){
            for (int j = 0; j < 10; j ++){
                for (int k = 0; k < 10; k ++){
                    if (k == j || k == i) continue;
                    if (k == a[n]){
                        dp[n][0][j][k] += dp[n - 1][0][i][j];
                    } 
                    dp[n][1][j][k] += dp[n - 1][1][i][j];
                    if (k < a[n]){
                        dp[n][1][j][k] += dp[n - 1][0][i][j];
                    }
                }
            }
        }
    }

    ll ret = 0;
    for (int i = 0; i < 10; i ++){
        for (int j = 0; j < 10; j ++){
            ret += dp[e][0][i][j] + dp[e][1][i][j];
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll l, r, ans = 0;
    cin >> l >> r; l --;
    if (r == 0){
        cout << 1 << '\n';
        return 0;
    }
    int sz = pre(r);
    ans += solve(1, sz);

    ll pw10 = 1, a9;
    for (int i = 1; i <= 18; i ++){
        pw10 *= 10ll;
        a9 = pw10 - 1ll;
        if (a9 < r){
            sz = pre(a9);
            ans += solve(1, sz);
        }
        else {
            break;
        }
    }

    if (l == -1) return cout << ans << '\n', 0;
    if (l == 0)  return cout << ans - 1 << '\n', 0;
    sz = pre(l);
    ans -= solve(1, sz);

    pw10 = 1;
    for (int i = 1; i <= 18; i ++){
        pw10 *= 10ll;
        a9 = pw10 - 1ll;
        if (a9 < l){
            sz = pre(a9);
            ans -= solve(1, sz);
        }
        else {
            break;
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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