Submission #648838

#	Time	Username	Problem	Language	Result	Execution time	Memory
648838		speedyArda	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	5 ms	1568 KiB

numbers

#pragma GCC optimize ("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
#define pb push_back
#define vll vector<long long>
#define vb vector<bool>
#define vi vector<int>
#define vs vector<string>
#define vpii vector< pair<int, int> >
#define pii pair<int, int>
#define pbb pair<bool, bool>
#define pll pair<long long, long long>
#define vvi vector< vector<int> > 
#define ld long double
#define mp make_pair
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

vi num;
ll dp[18][15][15][2][20]; // (pos) (last digit) (last  - 1 digit) (restricted) (digit count without beginning zeros)
ll a, b;

ll solve(int pos, int last, int beflast, int rest, int allzero)
{
    if(pos == num.size())
    {
       
        return 1;
    } 

    if(dp[pos][last][beflast][rest][allzero] != -1)
        return dp[pos][last][beflast][rest][allzero];
    
    ll res = 0;
    int limit;
    if(rest == 0)
        limit = num[pos];
    else
        limit = 9;
    for(int curr = 0; curr <= limit; curr++)
    {
        int newrest = rest;
        int newzero = allzero;
        if(rest == 0 && curr < limit)
            newrest = 1;
        if(allzero != 0)
            newzero++;
        else if(curr != 0)
            newzero = 1;
        if(newzero <= 1 || (newzero == 2 && last != curr)|| (last != curr && beflast != curr))
            res += solve(pos + 1, curr, last, newrest, newzero);
    }

    return dp[pos][last][beflast][rest][allzero] = res;
}

int main() 
{
    cin >> a >> b;
    memset(dp, -1, sizeof(dp));  
    a--;
    ll temp = a;
    while(temp > 0)
    {
        num.pb(temp % 10);
        temp /= 10;
    }  
    if(a == -1)
        num.pb(-1);    
    reverse(all(num));    
    ll left = solve(0, 0, 0, 0, 0);
    memset(dp, -1, sizeof(dp));
    temp = b;
    num.clear();
    while(temp > 0)
    {
        num.pb(temp % 10);
        temp /= 10;
    } 
    if(b == 0)
        num.pb(0);
    reverse(all(num));
    ll right = solve(0, 0, 0, 0, 0);
    cout << right - left << "\n";
}

Compilation message (stderr)

numbers.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
numbers.cpp: In function 'll solve(int, int, int, int, int)':
numbers.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if(pos == num.size())
      |        ~~~~^~~~~~~~~~~~~

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