제출 #596640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596640		__joyboy__	Palindrome-Free Numbers (BOI13_numbers)	C++14	66.67 / 100	22 ms	28504 KiB

numbers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define all(x) x.begin(), x.end()
#define nl '\n'
#define MOD1 1000000007
#define MOD2 998244353

#define f0r(a, b) for (long long a = 0; a < (b); ++a)
#define f1r(a, b, c) for (long long a = (b); a < (c); ++a)
#define f0rd(a, b) for (long long a = (b); a >= 0; --a)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define send                              \
    {                                     \
        ios_base::sync_with_stdio(false); \
    }
#define help            \
    {                   \
        cin.tie(NULL);  \
        cout.tie(NULL); \
    }
#define fix(prec)                            \
    {                                        \
        cout << setprecision(prec) << fixed; \
    }
#define mp make_pair
#define f first
#define s second
#define getunique(v)                      \
    {                                     \
        sort(all(v));                     \
        v.erase(unique(all(v)), v.end()); \
    }
#define readgraph(list, edges)      \
    for (int i = 0; i < edges; i++) \
    {                               \
        int a, b;                   \
        cin >> a >> b;              \
        a--;                        \
        b--;                        \
        list[a].pb(b);              \
        list[b].pb(a);              \
    }
#define ai(a, n)                      \
    for (int ele = 0; ele < n; ele++) \
        cin >> a[ele];
#define ain(a, lb, rb)                   \
    for (int ele = lb; ele <= rb; ele++) \
        cin >> a[ele];
#define ao(a, n)                            \
    {                                       \
        for (int ele = 0; ele < (n); ele++) \
        {                                   \
            if (ele)                        \
                cout << " ";                \
            cout << a[ele];                 \
        }                                   \
        cout << '\n';                       \
    }
#define aout(a, lb, rb)                          \
    {                                            \
        for (int ele = (lb); ele <= (rb); ele++) \
        {                                        \
            if (ele > (lb))                      \
                cout << " ";                     \
            cout << a[ele];                      \
        }                                        \
        cout << '\n';                            \
    }
#define vsz(x) ((long long)x.size())

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
const ll INF = 1e18;

template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v);
template <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v)
{
    cout << "[";
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ", ";
        cout << v[i];
    }
    return cout << "]";
}
template <typename A, typename B>
istream &operator>>(istream &cin, pair<A, B> &p)
{
    cin >> p.first;
    return cin >> p.second;
}

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...)                     \
    {                                 \
        cerr << "[" << #x << "] = ["; \
        _print(x);                    \
    }
#else
#define dbg(x...)
#endif

ll binpow(ll x, ll y) /* (x^y)%p in O(log y) */
{
    ll res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x);
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
ull binpowmod(ull x, ull y, ull p) /* (x^y)%p in O(log y) */
{
    ull res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
ll mod_inverse(ll n, ll p) /* Returns n^(-1) mod p */ { return binpowmod(n, p - 2, p); }
ll gcd(ll x, ll y)
{
    if (y == 0)
        return x;
    return gcd(y, x % y);
}
ll lcm(ll x, ll y)
{
    if (x == 0 || y == 0)
        return 0;
    else
        return x * y / gcd(x, y);
}
bool isPowerOfTwo(ll x)
{
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x & (x - 1)));
}

// struct custom_hash {
//     static uint64_t splitmix64(uint64_t x) {
//         // http://xorshift.di.unimi.it/splitmix64.c
//         x += 0x9e3779b97f4a7c15;
//         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
//         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
//         return x ^ (x >> 31);
//     }

//     size_t operator()(uint64_t x) const {
//         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
//         return splitmix64(x + FIXED_RANDOM);
//     }
// };

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

unsigned int onesComplement(unsigned int n)
{
    // Find number of bits in the given integer
    int number_of_bits = floor(log2(n)) + 1;

    // XOR the given integer with poe(2,
    // number_of_bits-1 and print the result
    return ((1 << number_of_bits) - 1) ^ n;
}

bool comp1(pair<ll, ll> x, pair<ll, ll> y)
{
    if (x.first != y.first)
        return x.first < y.first;
    return x.second > y.second;
}

// class cmp      //comrootator for priority_queue
// {               //declaration: priority_queue<int,vector<int>,cmp>
// public:
//     bool operator()(pair<ll, ll>& a, pair<ll, ll>& b)
//     {
//         // if(A.first == B.first)
//         //     return A.second < B.second;
//         return a.second > b.second;
//     }
// };

void printMSK(int msk)
{
    cout << "{ ";
    for (int i = 0; i < 32; ++i)
    {
        if (msk & (1LL << i))
            cout << i << ", ";
    }
    cout << " }";
}

void add(ll &a, ll b, ll MOD = MOD1)
{
    a += b;
    if (a < 0)
        a += MOD;
    if (a >= MOD)
        a -= MOD;
}

void _min(int &a, int b)
{
    a = min(a, b);
}

void KS(int t)
{
    cout << "Case #" << t << ": ";
}

ll ceil(ll n, ll r)
{
    return (n + r - 1) / r;
}

string num_to_str(ll num)
{
    string s = "";
    while (num)
    {
        s += '0' + num % 10;
        num /= 10;
    }
    reverse(all(s));
    return s;
}

ll str_to_num(string &s, int base_ = 10)
{
    ll num = 0;
    for (char c : s)
        num = num * base_ + c - '0';
    return num;
}

const ll nax = 20 ;
int n = 0;
ll dp[nax][nax][nax][nax][nax];
bool vs[nax][nax][nax][nax][nax];
int rec(int x, int l, int sl,bool s, bool z,string v){
    if(x==vsz(v)){vs[x][l][sl][s][z]=1;return dp[x][l][sl][s][z]=1;}
    if(vs[x][l][sl][s][z])return dp[x][l][sl][s][z];
    ll&ans = dp[x][l][sl][s][z];
    ans=0;
    int c = v[x]-'0';
    if(s)c=9;
    f0r(i,c+1){
        if(i==l||i==sl)continue;
        bool ns = 1;
        if((!s)&&i==c)ns=0;
        bool nz = z|(i^0);
        int nl1=i,nll=l;
        if((!z)&&(i==0))nl1=10,nll=10;
        ans+=rec(x+1,nl1,nll,ns,nz,v);
    }
    vs[x][l][sl][s][z]=1;
    return ans;
}

void solve(int tc = 1)  
{
    string a,b;
    cin>>a>>b;
    ll la = str_to_num(a);
    la--;
    a=num_to_str(la);
    memset(dp,0,sizeof(dp));
    memset(vs,0,sizeof(vs));
    ll ca = rec(0,10,10,0,0,b);
    memset(dp,0,sizeof(dp));
    memset(vs,0,sizeof(vs));
    ll cb = rec(0,10,10,0,0,a);
    dbg(ca,cb)
    cout<<ca-cb;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed << setprecision(7);
    int tc;
    tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; ++i)
    {
        dbg(i)
            solve(i);
    }
}

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