Submission #263242

#	Time	Username	Problem	Language	Result	Execution time	Memory
263242		Valera_Grinenko	Palindrome-Free Numbers (BOI13_numbers)	C++17	96.25 / 100	1 ms	404 KiB

numbers

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll dp[20][11][11][2]; //pos, prev1, prev2, (less?)
string s;
ll calc(int pos, int p2, int p1, bool l) {
  if(pos == s.size()) return 1;
  if(dp[pos][p2][p1][l] != -1) return dp[pos][p2][p1][l];
  int up = (l ? s[pos] - '0' : 9);
  ll tot = 0;
  for(int i = 0; i <= up; i++) {
    if((i == p1 && p1 != 10) || (i == p2 && p2 != 10)) continue;
    int cv = i;
    if(i == 0 && p1 == 10) cv = 10;
    tot += calc(pos + 1, p1, cv, l && cv == (s[pos] - '0'));
  }
  dp[pos][p2][p1][l] = tot;
  return tot;
}
int main() {

  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  ll a, b;

  cin >> a >> b;

  a--;

  s = to_string(b);

  memset(dp, -1, sizeof(dp));

  ll ans = calc(0, 10, 10, true);

  if(a > 0) {
    s = to_string(a);
    memset(dp, -1, sizeof(dp));
    ans -= calc(0, 10, 10, true);
  }

  cout << ans << endl;

  return 0;
}
/*

*/

Compilation message (stderr)

numbers.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
numbers.cpp: In function 'll calc(int, int, int, bool)':
numbers.cpp:34:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(pos == s.size()) return 1;
      |      ~~~~^~~~~~~~~~~

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