oj.uz

Submission #633670

# Submission time Handle Problem Language Result Execution time Memory
633670 2022-08-23T02:56:03 Z TAMREF Palindrome-Free Numbers (BOI13_numbers) C++17
100 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << '\n';
}
#ifdef TAMREF
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
#else
#define deb(...) 42
#endif
using ll = unsigned long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll dp[19][10][10]; // (digits left, prev^2 digit, prev digit)
ll dp_1d[19][10];
ll dp_0d[19];
ll ten[19] = {1};

ll solve(ll b) {
    ll ans = 0;
    for(int n = 18; n >= 0; n--) {
        debug("n = %d, ans = %llu\n", n, ans);
        ll qb = b / ten[n];
        if(qb == 0) continue;
        if(qb < 10) {
            debug("adding dp_0d[%d] = %llu\n", n, dp_0d[n]);
            ans += dp_0d[n];
            for(int i = 1; i < qb; i++) ans += dp_1d[n][i];
            continue;
        }
        for(int i = 0; i < qb % 10; i++) if(qb < 100 || i != (qb / 100) % 10) ans += dp[n][(qb / 10) % 10][i];
        if(qb % 10 == (qb / 10) % 10 || (qb >= 100 && qb % 10 == (qb / 100) % 10)) break;
    }
    debug("final ans = %llu\n", ans);
    return ans;
}

int main(){
    for(int i = 1; i < 19; i++) ten[i] = ten[i-1] * 10;
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            if(i == j) continue;
            dp[0][i][j] = 1;
        }
    }
    for(int n = 1; n < 19; n++) {
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < 10; j++) {
                if(i == j) continue;
                for(int k = 0; k < 10; k++) {
                    if(i == k ||j == k) continue;
                    dp[n][i][j] += dp[n-1][j][k];
                }
            }
        }
    }
    for(int i = 0; i < 10; i++) dp_1d[0][i] = 1;
    for(int n = 1; n < 19; n++) {
        for(int i = 1; i < 10; i++) {
            for(int j = 0; j < 10; j++) {
                if(i == j) continue;
                dp_1d[n][i] += dp[n-1][i][j];
            }
        }
    }
    dp_0d[0] = 1; // 0 is non-palindrome number
    for(int n = 1; n < 19; n++) {
        dp_0d[n] += dp_0d[n-1];
        for(int i = 1; i < 10; i++) {
            dp_0d[n] += dp_1d[n-1][i];
        }
    }
    ll a, b;
    cin >> a >> b;
    cout << solve(b+1) - solve(a) << '\n';
}

Compilation message

numbers.cpp: In function 'll solve(ll)':
numbers.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
numbers.cpp:54:9: note: in expansion of macro 'debug'
   54 |         debug("n = %d, ans = %llu\n", n, ans);
      |         ^~~~~
numbers.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
numbers.cpp:58:13: note: in expansion of macro 'debug'
   58 |             debug("adding dp_0d[%d] = %llu\n", n, dp_0d[n]);
      |             ^~~~~
numbers.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   60 |             for(int i = 1; i < qb; i++) ans += dp_1d[n][i];
      |                            ~~^~~~
numbers.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   63 |         for(int i = 0; i < qb % 10; i++) if(qb < 100 || i != (qb / 100) % 10) ans += dp[n][(qb / 10) % 10][i];
      |                        ~~^~~~~~~~~
numbers.cpp:63:59: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   63 |         for(int i = 0; i < qb % 10; i++) if(qb < 100 || i != (qb / 100) % 10) ans += dp[n][(qb / 10) % 10][i];
      |                                                         ~~^~~~~~~~~~~~~~~~~~
numbers.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
numbers.cpp:66:5: note: in expansion of macro 'debug'
   66 |     debug("final ans = %llu\n", ans);
      |     ^~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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