Submission #824800

#	Time	Username	Problem	Language	Result	Execution time	Memory
824800		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	908 KiB

numbers

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

int f[20][2][20][100];

int sus(const string &s, int id, bool smaller, int dig, int lst){
   if (f[id][smaller][dig][lst]!=-1) return f[id][smaller][dig][lst];
   if (id==sz(s)) return f[id][smaller][dig][lst]=1;
   int res=0;
   for (int i=0; i<=(smaller?9:s[id]-'0'); ++i){
      if (dig && i==lst%10) continue;
      if (dig>=2 && i==lst/10) continue;
      res+=sus(s, id+1, smaller|(i<s[id]-'0'), dig+(dig || i), (lst%10)*10+i);
   }
   return f[id][smaller][dig][lst]=res;
}

int calc(int x){
   if (x<0) return 0;
   stringstream ss; string s;
   ss << x; ss >> s;
   memset(f, -1, sizeof f);
   return sus(s, 0, 0, 0, 0);
}

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   int l, r; cin >> l >> r;
   cout << calc(r)-calc(l-1);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75