제출 #834553

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

numbers

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define fo(iter, start_value, less_than) for(int iter = start_value; iter<less_than; iter++)

#define noans cout<<"-1"
#define zero cout<<"0"
#define nline "\n"
#define space " "
#define MSBll(n) __lg(n)
#define vi vector<int> 
#define vpii vector<pair<int, int> > 
#define vvi vector<vector<int> > 
#define set_bits __builtin_popcountll
#define getunique(x) {sort(all(x)); x.erase(unique(all(x)), x.end());}
#define mem(x, val) memset(x, val, sizeof(x))

// const double PI = 3.1415926535897932384626433832795;
// const string pi = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";

const int mod = 1e9+7;
// const int mod = 998244353;
const ll INF = 1e18;
// const int N = 1e5+5;
// const int N = 2e5+5;
// const int N = 3e5+5;
// const int MX = INT_MAX;
// const int MN = INT_MIN;

#define int ll


mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int getRandomNumber(int l, int r){
   uniform_int_distribution<int> dist(l, r);
   return dist(rnd);
}


#define yes cout<<"YES"
#define no cout<<"NO"
//set MULTISET ka bhi dekh lena bhai

int dp[20][2][12][12];

int rec(int i, bool tight, int prv1, int prv2, bool s, const string &str, int n){
    if(i == n) return s;

    int &ans = dp[i][tight][prv1+2][prv2+2];
    if(ans != -1) return ans;
    ans = 0;
    int ub = (tight?(str[i] - '0'):9);

    for(int dig = 0; dig <= ub; dig++){
        if(dig == 0){
            if(!s){
                ans += rec(i+1, (tight&(dig == ub)), prv1, prv2, 0, str, n);
            }else{
                if(dig != prv1 and dig != prv2){
                    ans += rec(i+1, (tight&(dig == ub)), dig, prv1, (s or dig), str, n);
                }
            }
        }else{
            if(dig != prv1 and dig != prv2){
                ans += rec(i+1, (tight&(dig == ub)), dig, prv1, (s or dig), str, n);
            }
        }
    }
    return ans;
}

signed main() {
// #ifndef ONLINE_JUDGE
//  freopen("Error.txt", "w", stderr);
// #endif
    fastio();

    int l, r; cin>>l>>r;

    string rstr = to_string(r);

    int lans = 0, rans = 0;
    memset(dp, -1, sizeof dp);
    // rstr = "0000012";
    rans = rec(0, 1, -1, -2, 0, rstr, rstr.size());
    rans++;
    if(l){
        l--;
        memset(dp, -1, sizeof dp);
        string lstr = to_string(l);
        lans = rec(0, 1, -1, -2, 0, lstr, lstr.size());
        lans++;
    }
    cout<<(rans - lans);

    return 0;
}

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