제출 #499455

#제출 시각아이디문제언어결과실행 시간메모리
499455s_samchenkoPalindrome-Free Numbers (BOI13_numbers)C++17
100 / 100
1 ms340 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC target ("avx2") #define ll long long #define ff first #define ss second #define int ll #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define pii pair <int, int> #define pdd pair <double, double> #define vi vector <int> using namespace std; using namespace __gnu_pbds; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e12; const ll mod = 998244353; const int N = 2e5+100; int dp[10][10][20][2]; string st; int calc(int first, int second, int len, bool all){ if (len >= st.size()) return 1; if (dp[first][second][len][all] != -1) return dp[first][second][len][all]; int help = 0; if (all){ for (int n = 0; n <= 9; ++n) if (n != first && n != second) help += calc(second, n, len + 1, 1); } else{ int limit = st[len] - '0'; for (int n = 0; n < limit; ++n){ if (n != first && n != second) help += calc(second, n, len + 1, 1); } if (limit != first && limit != second) help += calc(second, limit, len + 1, 0); } return dp[first][second][len][all] = help; } int get(int n){ if (n < 0) return 0; memset(dp, -1, sizeof(dp)); st = to_string(n); int first = st[0] - '0', res = 1; for (int i = 1; i <= first; ++i){ res += calc(i, i, 1, i != first); } for (int k = 2; k <= st.size(); ++k){ for (int i = 1; i < 10; ++i) res += calc(i, i, k, 1); } return res; } void solve(){ int l, r; cin >> l >> r; cout << get(r) - get(l-1); } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tt = 1; //cin >> tt; while (tt--){ solve(); cout << '\n'; } }

컴파일 시 표준 에러 (stderr) 메시지

numbers.cpp: In function 'long long int calc(long long int, long long int, long long int, bool)':
numbers.cpp:28:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  if (len >= st.size()) return 1;
      |      ~~~~^~~~~~~~~~~~
numbers.cpp: In function 'long long int get(long long int)':
numbers.cpp:53:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int k = 2; k <= st.size(); ++k){
      |                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...