oj.uz

답안 #596637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596637 2022-07-14T23:12:48 Z __joyboy__ Palindrome-Free Numbers (BOI13_numbers) C++14
66.6667 / 100
 20 ms 28556 KB 
#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 = s||i<c;
        // 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);
    n=vsz(b);
    memset(dp,0,sizeof(dp));
    memset(vs,0,sizeof(vs));
    ll ca = rec(0,10,10,0,0,b);n = vsz(a);
    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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28452 KB Output is correct
2 Correct 17 ms 28412 KB Output is correct
3 Correct 15 ms 28416 KB Output is correct
4 Correct 14 ms 28492 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 15 ms 28416 KB Output is correct
7 Correct 18 ms 28556 KB Output is correct
8 Correct 14 ms 28500 KB Output is correct
9 Correct 15 ms 28508 KB Output is correct
10 Correct 14 ms 28480 KB Output is correct
11 Correct 15 ms 28500 KB Output is correct
12 Correct 15 ms 28492 KB Output is correct
13 Correct 15 ms 28500 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Correct 16 ms 28556 KB Output is correct
16 Correct 15 ms 28500 KB Output is correct
17 Correct 15 ms 28496 KB Output is correct
18 Correct 17 ms 28496 KB Output is correct
19 Correct 16 ms 28400 KB Output is correct
20 Correct 15 ms 28428 KB Output is correct

Subtask #2
41.6666666667 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Incorrect 17 ms 28388 KB Output isn't correct
3 Incorrect 17 ms 28500 KB Output isn't correct
4 Incorrect 16 ms 28544 KB Output isn't correct
5 Correct 15 ms 28500 KB Output is correct
6 Correct 16 ms 28500 KB Output is correct
7 Correct 15 ms 28492 KB Output is correct
8 Correct 18 ms 28496 KB Output is correct
9 Correct 15 ms 28500 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 15 ms 28416 KB Output is correct
12 Correct 14 ms 28492 KB Output is correct
13 Correct 15 ms 28412 KB Output is correct
14 Correct 14 ms 28500 KB Output is correct
15 Correct 15 ms 28500 KB Output is correct
16 Correct 16 ms 28504 KB Output is correct
17 Correct 17 ms 28492 KB Output is correct
18 Correct 17 ms 28412 KB Output is correct
19 Correct 16 ms 28404 KB Output is correct
20 Correct 16 ms 28500 KB Output is correct
21 Incorrect 17 ms 28500 KB Output isn't correct
22 Correct 16 ms 28500 KB Output is correct
23 Incorrect 16 ms 28484 KB Output isn't correct
24 Correct 15 ms 28456 KB Output is correct
25 Incorrect 15 ms 28496 KB Output isn't correct
26 Incorrect 16 ms 28508 KB Output isn't correct
27 Incorrect 16 ms 28448 KB Output isn't correct
28 Incorrect 16 ms 28500 KB Output isn't correct
29 Correct 16 ms 28500 KB Output is correct
30 Correct 18 ms 28492 KB Output is correct
31 Incorrect 17 ms 28472 KB Output isn't correct
32 Correct 17 ms 28496 KB Output is correct
33 Incorrect 15 ms 28504 KB Output isn't correct
34 Correct 16 ms 28500 KB Output is correct
35 Incorrect 16 ms 28392 KB Output isn't correct
36 Incorrect 16 ms 28500 KB Output isn't correct
37 Incorrect 15 ms 28500 KB Output isn't correct
38 Incorrect 16 ms 28508 KB Output isn't correct
39 Incorrect 16 ms 28500 KB Output isn't correct
40 Correct 16 ms 28512 KB Output is correct
41 Incorrect 15 ms 28428 KB Output isn't correct
42 Correct 20 ms 28508 KB Output is correct
43 Incorrect 17 ms 28500 KB Output isn't correct
44 Incorrect 20 ms 28496 KB Output isn't correct
45 Incorrect 17 ms 28508 KB Output isn't correct