Submission #1138230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138230		JelalTkm	Palindrome-Free Numbers (BOI13_numbers)	C++20	95 / 100	1 ms	328 KiB

numbers

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define int long long int
const int N = 3e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;

int dp[20][11][11];

int solve(string &num, int n, int pr1, int pr2, bool st, int tight) {
  if (n == 0) {
    // cout << '\n';
    return 1;
  }

  auto &el = dp[n][pr1][pr2];
  if (!tight && ~el) {
    // cout << '\n';
    return el;
  }

  int ub = (tight ? (num[(int) num.size() - n] - '0') : 9);
  int ans = 0;
  for (int dig = 0; dig <= ub; dig++) {
    if (dig != pr1 && dig != pr2) {
      // cout << dig;
      ans += solve(num, n - 1, ((st || dig > 0) ? dig : 10), pr1, (st | (dig > 0)) ,(tight & (dig == ub)));
    }
  }
  
  return el = ans;
}
int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    string l, r;
    cin >> l >> r;
    memset(dp, -1, sizeof(dp));
    int ansr = solve(r, (int) r.size(), 10, 10, 0, 1);
    int ansl = solve(l, (int) l.size(), 10, 10, 0, 1);
    bool ok = 1;
    for (int i = 1; i < (int) l.size(); i++) {
      if (l[i] == l[i - 1] || (i > 1 && l[i - 2] == l[i])) {
        ok = 0;
        break;
      }
    }
    cout << ansr - ansl + ok << '\n';
  }
  return 0;
}

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