Submission #1124058

#TimeUsernameProblemLanguageResultExecution timeMemory
1124058CDuongPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
2 ms584 KiB
/* #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") */ #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define i64 long long #define int long long #define isz(x) (int)x.size() using namespace std; const i64 inf = 1e18; void solve() { i64 l, r; cin >> l >> r; if (r == inf) --r; if (l == inf) --l; vector<i64> pw(19); pw[0] = 1; for (int i = 1; i < 19; ++i) { pw[i] = pw[i - 1] * 10; } vector odp(19, vector(11, vector(11, vector(2, -1ll)))); auto dp = odp; auto DP = [&](auto self, int lim, int len, int prv1, int prv2, int eq) -> i64 { if (dp[len][prv1][prv2][eq] != -1) { return dp[len][prv1][prv2][eq]; } if (len == 0) { int res = 0; for (int val = 0; val < (eq ? lim % 10 + 1 : 10); ++val) { if (val != prv1 and val != prv2) ++res; } return dp[len][prv1][prv2][eq] = res; } i64 res = 0; bool bf = (prv1 == 10 and prv2 == 10); if (not eq) { for (int val = 0; val < 10; ++val) if (val != prv1 and val != prv2) { res += self(self, lim, len - 1, prv2, (val == 0 and bf ? 10 : val), eq); } } else { int digit = (lim / pw[len]) % 10; for (int val = 0; val < digit; ++val) if (val != prv1 and val != prv2) { res += self(self, lim, len - 1, prv2, (val == 0 and bf ? 10 : val), 0); } if (digit != prv1 and digit != prv2) { res += self(self, lim, len - 1, prv2, (digit == 0 and bf ? 10 : digit), 1); } } return dp[len][prv1][prv2][eq] = res; }; auto calc = [&](int val) -> int { if (val == -1) return 0; dp = odp; return DP(DP, val, 17, 10, 10, 1); }; // cout << calc(999999999999999999) << endl; cout << calc(r) - calc(l - 1) << endl; } signed main() { #ifndef CDuongg if (fopen(taskname".inp", "r")) assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout)); #else freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); // cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; // cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...