Submission #1167145

#TimeUsernameProblemLanguageResultExecution timeMemory
1167145InvMODPalindrome-Free Numbers (BOI13_numbers)C++20
96.25 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) (int)(v).size() using ll = long long; // dp[pos][a[pos - 2]][a[pos - 1]][tight] // if it is not a palindrome then a[i] != a[i - 1] && a[i] != a[i - 2] ll dp[20][11][11][2]; ll calc_dp(vector<int> num, int pos = 0, int ppre = 10, int pre = 10, bool tight = true){ if(pos == sz(num)) return (min(ppre, pre) < 10); if(dp[pos][ppre][pre][tight] != -1) return dp[pos][ppre][pre][tight]; int lb = 0, ub = (tight) ? num[pos] : 9; ll answer = 0; for(int digit = lb; digit <= ub; digit++){ if(digit == pre || digit == ppre) continue; if(!digit && min(ppre, pre) == 10) continue; //cout << digit <<" " << (tight & (digit == ub)) << " " << pos <<" " << pre <<" " << ppre << "\n"; answer = answer + calc_dp(num, pos + 1, pre, digit, tight & (digit == ub)); } if(min(ppre, pre) == 10) answer = answer + calc_dp(num, pos + 1, 10, 10, false); return dp[pos][ppre][pre][tight] = answer; } ll calc(ll x){ if(x <= 0) return 0; vector<int> num; while(x){ num.push_back(x % 10); x /= 10; } reverse(num.begin(), num.end()); memset(dp, -1, sizeof(dp)); return calc_dp(num); } void solve() { ll a,b; cin >> a >> b; //cout << calc(a - 1) <<" " << calc(b) << "\n"; cout << calc(b) - calc(a - 1) << "\n"; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "InvMOD" if(fopen(name".INP", "r")){ freopen(name".INP","r",stdin); freopen(name".OUT","w",stdout); } int t = 1; //cin >> t; while(t--) solve(); return 0; }

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...