Submission #1121071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121071		vjudge1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	592 KiB

numbers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 19;
ll pw[N];
bool good(string a)
{
    for (ll i = 0; i + 1 < a.size(); i++)
        if (a[i] == a[i + 1]) return false;
    for (ll i = 0; i + 2 < a.size(); i++)   if (a[i] == a[i + 2]) return false;
    return true;
}
ll f(ll x)
{
    if (x == -1)
        return 0;
    ll ans = 0;
    string a = to_string(x);
    if (a.size() == 1) return x + 1;
    for (ll i = 0; i < a.size(); i++)
        for (char d = '0' + (i == 0); d < a[i]; d++)
                if (good(a.substr(0, i) + d))
                {
                    if (i == 0) ans += 9 * pw[a.size() - 2];
                    else ans += pw[a.size() - i - 1];
                }
    if (a.size() == 2) ans += 10;
    else 
    {
        for (ll i = 1; i + 1 < a.size(); i++) ans += 9 * 9 * pw[a.size() - i - 2];
        ans += 10;
    }
    ans += good(a);
    return ans;
}
void solve()
{
    ll l, r;
    cin >> l >> r;
    pw[0] = 1;
    for (ll i = 1; i < N; i++) pw[i] = pw[i - 1] * 8;
    cout << f(r) - f(l - 1) << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Compilation message (stderr)

numbers.cpp: In function 'bool good(std::string)':
numbers.cpp:17:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (ll i = 0; i + 1 < a.size(); i++)
      |                    ~~~~~~^~~~~~~~~~
numbers.cpp:19:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (ll i = 0; i + 2 < a.size(); i++)   if (a[i] == a[i + 2]) return false;
      |                    ~~~~~~^~~~~~~~~~
numbers.cpp: In function 'long long int f(long long int)':
numbers.cpp:29:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (ll i = 0; i < a.size(); i++)
      |                    ~~^~~~~~~~~~
numbers.cpp:39:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (ll i = 1; i + 1 < a.size(); i++) ans += 9 * 9 * pw[a.size() - i - 2];
      |                        ~~~~~~^~~~~~~~~~

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