Submission #778987

#TimeUsernameProblemLanguageResultExecution timeMemory
778987vjudge1Palindrome-Free Numbers (BOI13_numbers)C++14
100 / 100
1 ms340 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long #define f first #define s second #define pii pair<int,int> #define piii pair<int,pair<int,int>> #define vii vector<vector<int>> #define vi vector<int> #define cd complex<double> #define endl '\n' //#define multipletest using namespace std; const int LIM=5e3; const int INF = 1e18; const string name="template"; int n,m,l,r; string t; int memo[20][11][11][2][2]; int dp(int pos,int lst1,int lst2,int eq,int start){ // cout<<pos<<" "<<lst1<<" "<<lst2<<" "<<eq<<" "<<start<<endl; if(pos==t.size()){ return 1; } if(memo[pos][lst1+1][lst2+1][eq][start]!=-1){ return memo[pos][lst1+1][lst2+1][eq][start]; } int ans=0; if(start==0){ if(eq==true){ ans+=dp(pos+1,-1,-1,false,false); int lim=t[pos]-'0'; for(int i=1;i<=lim;++i){ ans+=dp(pos+1,i,-1,(i==lim),true); } } else{ ans+=dp(pos+1,-1,-1,false,false); for(int i=1;i<=9;++i){ ans+=dp(pos+1,i,-1,false,true); } } } else{ if(eq==true){ 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 memo[pos][lst1+1][lst2+1][eq][start]=ans; } int DP_digit(int x){ if(x<0){ return 0; } t=to_string(x); memset(memo,-1,sizeof(memo)); return dp(0,-1,-1,true,0); } void solve(){ //CODE GOES HERE cin>>l>>r; cout<<DP_digit(r) - DP_digit(l-1)<<endl; } signed main(){ // freopen((name+".inp").c_str(),"r",stdin); // freopen((name+".out").c_str(),"w",stdout); // ifstream cin(".txt"); // ofstream cout(".txt"); //ifstream cin((name +".inp")); //ofstream cout((name +".ans")); ios_base::sync_with_stdio(false); cin.tie(NULL); int test; test=1; #ifdef multipletest cin>>test; #endif while(test--){ solve(); #ifdef DEBUG cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl; #endif } }

Compilation message (stderr)

numbers.cpp: In function 'long long int dp(long long int, long long int, long long int, long long int, long long int)':
numbers.cpp:23:11: 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]
   23 |     if(pos==t.size()){
      |        ~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...