oj.uz

Submission #968070

# Submission time Handle Problem Language Result Execution time Memory
968070 2024-04-23T07:31:35 Z Whisper Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 532 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 376 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 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 352 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 352 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 388 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 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 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 344 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 532 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 468 KB Output is correct
45 Correct 1 ms 348 KB Output is correct