Submission #648830

#	Time	Username	Problem	Language	Result	Execution time	Memory
648830		speedyArda	Palindrome-Free Numbers (BOI13_numbers)	C++14	71.25 / 100	1 ms	356 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][10][10][2]; // pos last digit last  - 1 digit restricted
ll a, b;

ll solve(int pos, int last, int beflast, int rest)
{
    if(pos == num.size())
    {
        //if(pos == 1 || (pos == 2 && last != digit) || (pos > 2 && last != digit && beflast != digit))
            return 1;
        //return 0;
    }    

    if(dp[pos][last][beflast][rest] != -1)
        return dp[pos][last][beflast][rest];
    
    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 newlast = digit;
        if(rest == 0 && curr < limit)
            newrest = 1;
        if(pos == 0 || (pos == 1 && last != curr) || (pos > 1 && last != curr && beflast != curr))
            res += solve(pos + 1, curr, last, newrest);
    }

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

int main() 
{
    cin >> a >> b;
    memset(dp, -1, sizeof(dp));  
    a--;
    ll temp = a;
    while(temp > 0)
    {
        num.pb(temp % 10);
        temp /= 10;
    }      
    reverse(all(num));    
    ll left = solve(0, 0, 0, 0);
    memset(dp, -1, sizeof(dp));
    temp = b;
    num.clear();
    while(temp > 0)
    {
        num.pb(temp % 10);
        temp /= 10;
    } 
    reverse(all(num));
    ll right = solve(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)':
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: 11.25 / 25
• Subtask 2: 60 / 75