제출 #383256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383256		Sara	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	512 KiB

numbers

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long int
#define F first
#define S second
#define pb push_back

const ll N = 3e5 + 5;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;

ll dp[20][2][10][10];

// 50 -> tool
// 2 -> koochiktar shode?
// 20 -> raghame yeki moonde be akhar
// 20 raghame akhar

int l[20], r[20], tmp[20], a[20];

inline int pre(ll x){
    int cur = -1;
    fill(tmp, tmp + 20, 0);
    for (int i = 18; i >= 1; i --){
        if ((x == 0) && (cur == -1)){
            cur = i;
        }
        tmp[i] = x % 10; 
        x /= 10ll;
    }
    fill(a, a + 20, 0);
    for (int i = 1; cur + i <= 18; i ++){
        a[i] = tmp[cur + i];
    }
    return 18 - cur;
}

inline ll solve(int s, int e){

    if (e - s + 1 == 1){
        return a[1] + 1;
    }

    memset(dp, 0, sizeof dp);

    if (a[1] != a[2]){
        dp[2][0][a[1]][a[2]] ++;
    } 
    s += 2;
    for (int i = 1; i < 10; i ++){
        for (int j = 0; j < 10; j ++){
            if (i == j) continue;
            if (i < a[1] || (i == a[1] && j < a[2])){
                dp[2][1][i][j] ++;
            }
        }
    }

    for (int n = s; n <= e; n ++){
        for (int i = 0; i < 10; i ++){
            for (int j = 0; j < 10; j ++){
                for (int k = 0; k < 10; k ++){
                    if (k == j || k == i) continue;
                    if (k == a[n]){
                        dp[n][0][j][k] += dp[n - 1][0][i][j];
                    } 
                    dp[n][1][j][k] += dp[n - 1][1][i][j];
                    if (k < a[n]){
                        dp[n][1][j][k] += dp[n - 1][0][i][j];
                    }
                }
            }
        }
    }

    ll ret = 0;
    for (int i = 0; i < 10; i ++){
        for (int j = 0; j < 10; j ++){
            ret += dp[e][0][i][j] + dp[e][1][i][j];
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll l, r, ans = 0;
    cin >> l >> r; l --;
    if (r == 0){
        cout << 1 << '\n';
        return 0;
    }
    int sz = pre(r);
    ans += solve(1, sz);

    ll pw10 = 1, a9;
    for (int i = 1; i <= 18; i ++){
        pw10 *= 10ll;
        a9 = pw10 - 1ll;
        if (a9 < r){
            sz = pre(a9);
            ans += solve(1, sz);
        }
        else {
            break;
        }
    }

    if (l == -1) return cout << ans << '\n', 0;
    if (l == 0)  return cout << ans - 1 << '\n', 0;
    sz = pre(l);
    ans -= solve(1, sz);

    pw10 = 1;
    for (int i = 1; i <= 18; i ++){
        pw10 *= 10ll;
        a9 = pw10 - 1ll;
        if (a9 < l){
            sz = pre(a9);
            ans -= solve(1, sz);
        }
        else {
            break;
        }
    }
    cout << ans << '\n';
    return 0;
}        

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