Submission #779945

#TimeUsernameProblemLanguageResultExecution timeMemory
779945vjudge1Palindrome-Free Numbers (BOI13_numbers)C++17
100 / 100
1 ms340 KiB
//#pragma GCC optimize("conserve-stack,no-stack-protector") #pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native") #include<bits/stdc++.h> #define pii pair<int, int> #define fi first #define se second #define pb push_back #define int long long //#define mod 998244353 using namespace std; using ll=long long; const int MN=1025; int dp[20][11][11][2][2]; string t; //const int inf = 1e18; int DP(int pos, int lst1, int lst2, bool eq, bool start) { if(pos==t.size()) return 1; if(dp[pos][lst1+1][lst2+1][eq][start]!=-1) return dp[pos][lst1+1][lst2+1][eq][start]; int ans=0; if(!start) { ans+=DP(pos+1,-1,-1,false,false); if(eq) { int limit=t[pos]-'0'; for (int i=1; i<=limit; i++) { ans+=DP(pos+1,i,-1,(i==limit),true); } } else { for (int i=1; i<=9; i++) { ans+=DP(pos+1,i,-1,false,true); } } } else { if(eq) { int limit=t[pos]-'0'; for (int i=0; i<=limit; i++) { if(i==lst1||i==lst2) continue; ans+=DP(pos+1,i,lst1,(i==limit), true); } } else { for (int i=0; i<=9; i++) { if(i==lst1||i==lst2) continue; ans+=DP(pos+1,i,lst1,false,true); } } } return dp[pos][lst1+1][lst2+1][eq][start]=ans; } int dp_digit(int x) { if(x<0) return 0; t=to_string(x); memset(dp,-1,sizeof(dp)); return DP(0,-1,-1,1,0); } inline void solve() { int l,r; cin>>l>>r; cout<<dp_digit(r)-dp_digit(l-1); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t=1; // cin>>t; while(t--) { solve(); } }

Compilation message (stderr)

numbers.cpp: In function 'long long int DP(long long int, long long int, long long int, bool, bool)':
numbers.cpp:18:8: 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]
   18 |  if(pos==t.size()) return 1;
      |     ~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...