Submission #860108

#	Time	Username	Problem	Language	Result	Execution time	Memory
860108		Ellinor	Palindrome-Free Numbers (BOI13_numbers)	C++14	62.92 / 100	1 ms	600 KiB

numbers

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <cstdlib>
#include <set>
#include <iomanip>
#include <limits>
#include <map>
#include <assert.h>
#include <algorithm>
#include <list>
#include <iterator>
#include <fstream>
#include <random>
#include <unordered_map>
#include <array>
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

//

ll a, b;

vector<int> digits;

vector<vector<vector<vector<ll>>>> dp;


void digify(ll number)
{
    digits.clear();

    while(number > 0)
    {
        digits.push_back(number % 10); //push the last digit in
        number /= 10; //truncate the digit
    }
    reverse(digits.begin(), digits.end());
}


// int GetNumberOfDigits (ll i)
// {
//     return i > 0 ? (int) log10 ((double) i) + 1 : 1;
// }


ll rec(int at, bool edgy, int d2, int d1)
{
    if (at == digits.size()) return 1;

    if (dp[at][edgy][d2 == -1 ? 10 : d2][d1 == -1 ? 10 : d1] != -1) return dp[at][edgy][d2][d1];

    ll ret = 0;
    rep(d,0, edgy ? digits[at] + 1 : 10)
    {
        if (d == d2 || d == d1) continue;

        bool new_edgy = edgy && (d == digits[at]);
        bool leading_zero = d1 == -1 && d == 0;

        ret += rec(at + 1, new_edgy, d1, leading_zero ? -1 : d);
    }

    dp[at][edgy][d2 == -1 ? 10 : d2][d1 == -1 ? 10 : d1] = ret;
    return ret;
}

int32_t main()
{
    cerr << "hi :) ";
    fast();
    cin >> a >> b;

    digify(a - 1);

    cerr << digits.size() << "\n";
    rep(i,0,digits.size()) {
        cerr << digits[i] << " ";
    }
    cerr << "\n";

    dp.assign(digits.size(), vector<vector<vector<ll>>>(2, vector<vector<ll>>(11, vector<ll>(11, -1))));
    int aans = rec(0, true, -1, -1); // a-1

    cerr << aans << "\n";
    
    digify(b);
    dp.assign(digits.size(), vector<vector<vector<ll>>>(2, vector<vector<ll>>(11, vector<ll>(11, -1))));
    int bans = rec(0, true, -1, -1); // b

    cerr << bans << "\n";

    ll ans = bans - aans;
    cout << ans << "\n";
}

Compilation message (stderr)

numbers.cpp: In function 'll rec(int, bool, int, int)':
numbers.cpp:71:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     if (at == digits.size()) return 1;
      |         ~~~^~~~~~~~~~~~~~~~

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