// #include <iostream>
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe") // byte swap
#pragma GCC target("aes,pclmul,rdrnd") // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
ll INF = 1000000000;
ll mod = 1e9 + 7;
//
ll a, b;
vector<int> digits;
vector<vector<vector<vector<ll>>>> dp;
void digify(ll number)
{
digits.clear();
digits = {};
while(number > 0)
{
digits.push_back(number % 10); //push the last digit in
number /= 10; //truncate the digit
}
reverse(digits.begin(), digits.end());
}
// int GetNumberOfDigits (ll i)
// {
// return i > 0 ? (int) log10 ((double) i) + 1 : 1;
// }
ll rec(int at, bool edgy, int d2, int d1)
{
if (at == digits.size()) return 1;
if (dp[at][edgy ? 1 : 0][d2 == -1 ? 10 : d2][d1 == -1 ? 10 : d1] != -1) return dp[at][edgy][d2][d1]; // bool ind ?
ll ret = 0;
rep(d,0, edgy ? digits[at] + 1 : 10)
{
if (d == d2 || d == d1) continue;
bool new_edgy = edgy && (d == digits[at]);
bool leading_zero = d1 == -1 && d == 0;
ret += rec(at + 1, new_edgy, d1, leading_zero ? -1 : d);
}
dp[at][edgy ? 1 : 0][d2 == -1 ? 10 : d2][d1 == -1 ? 10 : d1] = ret;
return ret;
}
int32_t main()
{
// cerr << "hi :) ";
fast();
cin >> a >> b;
ll aans = 0;
if (a != 0) {
digify(a - 1);
cerr << digits.size() << "\n";
rep(i,0,digits.size()) {
cerr << digits[i] << " ";
}
cerr << "\n";
dp.assign(digits.size(), vector<vector<vector<ll>>>(2, vector<vector<ll>>(11, vector<ll>(11, -1))));
aans = rec(0, true, -1, -1); // a-1
}
cerr << aans << "\n";
digify(b);
cerr << digits.size() << "\n";
rep(i,0,digits.size()) {
cerr << digits[i] << " ";
}
cerr << "\n";
dp.assign(digits.size(), vector<vector<vector<ll>>>(2, vector<vector<ll>>(11, vector<ll>(11, -1))));
ll bans = rec(0, true, -1, -1); // b
cerr << bans << "\n";
ll ans = bans - aans;
cout << ans << "\n";
}
Compilation message
numbers.cpp: In function 'll rec(int, bool, int, int)':
numbers.cpp:55:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (at == digits.size()) return 1;
| ~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
0 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
420 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
508 KB |
Output is correct |
| 26 |
Correct |
1 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
600 KB |
Output is correct |
| 29 |
Correct |
1 ms |
348 KB |
Output is correct |
| 30 |
Correct |
1 ms |
348 KB |
Output is correct |
| 31 |
Correct |
1 ms |
348 KB |
Output is correct |
| 32 |
Correct |
1 ms |
348 KB |
Output is correct |
| 33 |
Correct |
1 ms |
348 KB |
Output is correct |
| 34 |
Correct |
1 ms |
348 KB |
Output is correct |
| 35 |
Correct |
0 ms |
348 KB |
Output is correct |
| 36 |
Correct |
1 ms |
348 KB |
Output is correct |
| 37 |
Correct |
0 ms |
348 KB |
Output is correct |
| 38 |
Correct |
1 ms |
348 KB |
Output is correct |
| 39 |
Correct |
0 ms |
348 KB |
Output is correct |
| 40 |
Correct |
0 ms |
348 KB |
Output is correct |
| 41 |
Correct |
1 ms |
348 KB |
Output is correct |
| 42 |
Correct |
1 ms |
348 KB |
Output is correct |
| 43 |
Correct |
1 ms |
348 KB |
Output is correct |
| 44 |
Correct |
1 ms |
348 KB |
Output is correct |
| 45 |
Correct |
1 ms |
348 KB |
Output is correct |
