Submission #779719

#TimeUsernameProblemLanguageResultExecution timeMemory
779719SteGGPalindrome-Free Numbers (BOI13_numbers)C++17
100 / 100
1 ms468 KiB
//Judges with GCC >= 12 only needs Ofast //#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize") //MLE optimization //#pragma GCC optimize("conserve-stack") //Old judges //#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2") //New judges. Test with assert(__builtin_cpu_supports("avx2")); //#pragma GCC target("arch=skylake") //Atcoder //#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma") #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; //template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //write variables and debug #define bugf cout << "Here" << endl #define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__) template<class T, class U> ostream& operator<<(ostream& output, const pair<T, U> &A){ output << "(" << A.first << ", " << A.second << ")"; return output; } template <class T> ostream& operator<<(ostream& output, const vector<T> &arr){ int n = arr.size(); output << "["; for(int i = 0; i < n; i++){ output << arr[i]; if(i != n - 1) output << ", "; } output << "]"; return output; } template<class T> ostream& operator<<(ostream& output, const set<T> &s){ output << "{"; for(auto it = s.begin(); it != s.end(); it++){ if(it != s.begin()) output << ", "; output << (*it); } output << "}"; return output; } template<class T, class U> ostream& operator<<(ostream& output, const map<T, U> &m){ output << "{"; for(auto it = m.begin(); it != m.end(); it++){ if(it != m.begin()) output << ", "; output << "(" << it->first << " : " << it->second << ")"; } output << "}"; return output; } template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << " = " << h << endl; } template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg != ',')cout << *sdbg++; cout << " = " << h << "\n"; _dbg(sdbg+1, a...); } template<class _Arr, class _Index> void _dbg_arr(_Arr arr, _Index index){ cout << '[' << index << "] = " << arr[index] << endl; } template<class _Arr, class _Index, class... TA> void _dbg_arr(_Arr &arr, _Index index, TA... args){ cout << '[' << index << ']'; _dbg_arr(arr[index], args...); } //open file #define taskname "" //name input and output file #ifdef SteGG void open(){ if(fopen("input.inp", "r")){ freopen("input.inp", "r", stdin); //freopen("output.out", "w", stdout); } } #else void open(){ if(fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } } #endif //initialize #define testcase \ long long test; \ cin >> test; \ for(int tst = 1; tst <= test; tst++) #define int long long #define MOD 1000000007 #define FFTMOD (119 << 23 | 1) #define EPSILON 1e-9 #define setpre(x) fixed << setprecision(x) #define cd complex<double> #define all(x) x.begin(), x.end() const long long INF = 3e18L + 5; const int inf = 1e9 + 7; const double infd = 1e60; const double PI = acos(-1); const int maxn = 1e5 + 5; //const int base = ; string l, r; int n; int dp[20][2][2][11][11][2]; //others struct or class //others function //others init signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); open(); cin >> l >> r; n = r.size(); while(l.size() < n){ l = '0' + l; } memset(dp, -1, sizeof(dp)); auto solve = [&](auto &&solve, int index, int checkl, int checkr, int l_1, int l_2, int in_num) -> int { if(index == n) return 1; if(dp[index][checkl][checkr][l_1 + 1][l_2 + 1][in_num] != -1) return dp[index][checkl][checkr][l_1 + 1][l_2 + 1][in_num]; int result = 0; for(int d = 0; d < 10; d++){ if(d == l_1 || d == l_2) continue; if(checkl && l[index] - '0' > d) continue; if(checkr && r[index] - '0' < d) continue; in_num |= (d != 0); if(in_num){ result += solve(solve, index + 1, checkl & (l[index] - '0' == d), checkr & (r[index] - '0' == d), l_2, d, in_num); }else{ result += solve(solve, index + 1, checkl & (l[index] - '0' == d), checkr & (r[index] - '0' == d), l_1, l_2, in_num); } } return dp[index][checkl][checkr][l_1 + 1][l_2 + 1][in_num] = result; }; cout << solve(solve, 0, 1, 1, -1, -1, 0) << endl; return 0; }

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:143:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  143 |  while(l.size() < n){
      |        ~~~~~~~~~^~~
numbers.cpp: In function 'void open()':
numbers.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...