oj.uz

Submission #899633

# Submission time Handle Problem Language Result Execution time Memory
899633 2024-01-06T15:39:23 Z wksp Palindrome-Free Numbers (BOI13_numbers) C++14
22.5 / 100
 1 ms 756 KB 
#include<bits/stdc++.h>
using namespace std;


long long dp[25][11]; // position, letter (0-9)
long long dp_static[25][11];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    long long a, b;
    cin >> a >> b;
    a--;
    vector<int> a_ve;
    vector<int> b_ve;
    while(a > 0){
        a_ve.push_back(a%10);
        a /= 10;
    }
    while(b > 0){
        b_ve.push_back(b%10);
        b /= 10;
    }
    reverse(a_ve.begin(), a_ve.end());
    reverse(b_ve.begin(), b_ve.end());
    for(int i = 0; i < 10; i++){
        dp[1][i] = i;
        dp_static[1][i] = 1;
    }
    for(int i = 2; i < 20; i++){
        dp[i][0] = dp[i-1][9];
        for(int j = 1; j < 10; j++){
            dp_static[i][j] = dp[i][0] - dp_static[i-1][j] - dp_static[i-2][j];
            dp[i][j] = dp[i][j-1] + dp_static[i][j]; 
        }
    }
    int last = -1;
    int last_second = -1;
    int nr = a_ve.size() + 1;
    long long ans_a = 0;
    bool update = true;
    for(auto u: a_ve){
        nr--;
        if(last == u or last_second == u){
            update = false;
            break;
        }
        if(u == 0){
            last_second = last;
            last = u;
            continue;
        }
        ans_a += dp[nr][u-1];
        if(last != -1){
            ans_a -= dp_static[nr-1][last];
        }
        if(last != -1 and last < u){
            ans_a -= dp_static[nr][last];
        }
        if(last_second != -1 and last_second < u){
            ans_a -= dp_static[nr][last_second];
        }

        last_second = last;
        last = u;
    }
    if(update){
        ans_a++;
    }   
    update = true;
    last = -1;
    last_second = -1;
    nr = b_ve.size() + 1;
    long long ans_b = 0;
    for(auto u: b_ve){
        nr--;
        if(last == u or last_second == u){
            update = false;
            break;
        }
        if(u == 0){
            last_second = last;
            last = u;
            continue;
        }
        ans_b += dp[nr][u-1];
        if(last != -1){
            ans_b -= dp_static[nr-1][last];
        }
        if(last != -1 and last < u){
            ans_b -= dp_static[nr][last];
        }
        if(last_second != -1 and last_second < u){
            ans_b -= dp_static[nr][last_second];
        }

        last_second = last;
        last = u;
    }
    if(update){
        ans_b++;
    }
    long long ans = ans_b - ans_a;
    cout << ans << '\n';





    return 0;
}

Subtask #1
2.5 / 25.0

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

Subtask #2
20.0 / 75.0

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