Submission #1120665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120665		Mamedov	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	508 KiB

numbers

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
//#define pbase 361549
//#define imod 1073737591
//#define uimod 2147479307u
//#define llmod 292187309552789533ll


using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << ln;
}

const int MAX = 20;
const int D = 11;
ll dp[MAX][D][D][2];

ll solve(string &s, int pos, int d1, int d2, int strict) {  /// digits in [1, 10], use 0 for no digit
  if (size(s) == pos) return 1;
  if (dp[pos][d1][d2][strict] != -1) return dp[pos][d1][d2][strict];
  ll res = 0;
  if (!d2) res += solve(s, pos + 1, d1, d2, 0);
  int st = 1 + (!d2 ? 1 : 0);
  if (!strict) {
    for (int d3 = st; d3 < D; ++d3) {
      if (d3 != d1 && d3 != d2) res += solve(s, pos + 1, d2, d3, 0);
    }
  } else {
    int d = s[pos] - '0' + 1;
    for (int d3 = st; d3 <= d; ++d3) {
      if (d3 != d1 && d3 != d2) {
        if (d3 == d) res += solve(s, pos + 1, d2, d3, 1);
        else res += solve(s, pos + 1, d2, d3, 0);
      }
    }
  }
  return dp[pos][d1][d2][strict] = res;
}
ll palFree(ll n) {
  if (n < 0) return 0;
  string s = to_string(n);
  for (int i = 0; i < MAX; ++i) {
    for (int d1 = 0; d1 < D; ++d1) {
      for (int d2 = 0; d2 < D; ++d2) {
        for (int k = 0; k < 2; ++k) {
          dp[i][d1][d2][k] = -1;
        }
      }
    }
  }
  return solve(s, 0, 0, 0, 1);
}
void solve() {
  ll a, b;
  cin >> a >> b;
  cout << palFree(b) - palFree(a - 1) << ln;
}
int main() {
  iospeed;
  solve();
  return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75