Submission #939105

#TimeUsernameProblemLanguageResultExecution timeMemory
939105tamir1Palindrome-Free Numbers (BOI13_numbers)C++17
100 / 100
1 ms600 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; ll a,b,dp[20][2][2][2]; vector<ll> v; void build(ll a){ if(a<10){ v.push_back(a); return; } build(a/10); v.push_back(a%10); } ll rec(ll idx,ll t,ll s,ll u,ll last1,ll last2){ if(idx==v.size()) return 1; if(dp[idx][t][s][u]!=-1) return dp[idx][t][s][u]; ll i,up=9,ans=0; if(!t) up=v[idx]; for(i=0;i<=up;i++){ if(s && last2==i) continue; if(u && last1==i) continue; ans+=rec(idx+1,t|(i<up),s|(i>0),u|s,last2,i); } return dp[idx][t][s][u]=ans; } ll solve(ll a){ if(a==-1) return 0; v.clear(); build(a); memset(dp,-1,sizeof dp); return rec(0,0,0,0,0,0); } int main(){ cin >> a >> b; cout << solve(b)-solve(a-1); }

Compilation message (stderr)

numbers.cpp: In function 'long long int rec(long long int, long long int, long long int, long long int, long long int, long long int)':
numbers.cpp:15:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(idx==v.size()) return 1;
      |     ~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...