oj.uz

Submission #518281

# Submission time Handle Problem Language Result Execution time Memory
518281 2022-01-23T10:13:43 Z Ai7081 Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;
#define long long long
const bool debug = 0;

long a, b, pow8[20], dp[20][15][15], d[20][15], sum[20][15];

long round(long x, long k) {
    x /= pow(10, k);
    return x * pow(10, k);
}

bool check(long x) {
    long p = -1, q = -1;
    while (x > 0) {
        if (x%10 == p || x%10 == q) return false;
        q = p;
        p = x%10;
        x /= 10;
    }
    return true;
}

long until(long x) {
    if (x < 10) return x+1;
    long tmp = x;
    vector<long> unit;
    while (x > 0) unit.push_back(x%10), x/=10;

    long ret = sum[unit.size()][unit[unit.size()-1] - 1];
    if (debug) cout << ret << endl;

    for (int j=0; j<unit[unit.size()-2]; j++) {
        ret += dp[unit.size()][unit[unit.size()-1]][j];
        if (debug) cout << unit.size() << ' ' << unit[unit.size()-1] << ' ' << j << ' ' << ret << endl;
    }

    for (int i=unit.size()-2; i>=1; i--) {
        if (!check(tmp / pow(10, i))) break;
        for (int j=0; j<unit[i-1]; j++) {
            if (j != unit[i+1]) {
                ret += dp[i+1][unit[i]][j];
                if (debug) cout << i+1 << ' ' << unit[i] << ' ' << j << ' ' << ret << endl;
            }
        }
    }

    ret += check(tmp);
    if (debug) cout << ret << endl;
    return ret;
}

long sol(long x, long y) {
    if (!x) return until(y);
    return until(y) - until(x-1);
}

int main() {
    pow8[0] = 1;
    for (int i=1; i<=18; i++) pow8[i] = pow8[i-1] * 8;
    for (int i=0; i<=9; i++) for (int j=0; j<=9; j++) if (i!=j) dp[2][i][j] = 1;
    for (int u=3; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) {
                if (i!=j) {
                    for (int k=0; k<=9; k++) {
                        if (i!=k && j!=k) dp[u][i][j] += dp[u-1][j][k];
                    }
                }
            }
        }
    }
    for (int i=0; i<=9; i++) d[1][i] = 1;
    for (int u=2; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            for (int j=0; j<=9; j++) {
                d[u][i] += dp[u][i][j];
            }
        }
    }
    sum[1][0] = 1;
    for (int u=1; u<=18; u++) {
        for (int i=0; i<=9; i++) {
            if (!i && u!=1) sum[u][i] = sum[u-1][9];
            else sum[u][i] = sum[u][i-1] + d[u][i];
        }
    }
/*
    long expect = 0;
    for (long i=0; i<=100000000; i++) {
        expect += check(i);
        if (expect != until(i)) {
            cout << "============ bomb at " << i  << " =============" << endl;
        }
        if (!(i%1000000)) cout << "reach " << i << endl;
    }
*/

    scanf(" %lld %lld", &a, &b);
    printf("%lld", sol(a, b));

}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf(" %lld %lld", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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