제출 #1284395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284395		vidush.rk11	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	2 ms	580 KiB

numbers

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>
#include <queue>
#include <numeric>
#include <cassert>
#include <list>
#include <iomanip>
#include <unordered_set>

//#include <bit>
//#include <bitset>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define pb push_back
#define pq priority_queue<ll>

#define tl tuple<int,int,ll>
#define ld long double
//#define int ll
#define p pair<int,int>
#define tu tuple<int,int,int,int,int>
#define mod1 998244353
#define mod2 1000000007
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

int nmax = 2e5 + 5;
using namespace std;



//long long power(long long a, long long b, long long m){
//    if (b==0) return 1;
//    if (b==1) return a%m;
//    
//    long long temp=power(a,b/2,m)%m;
//    if (b%2) return (temp*temp*a)%m;
//    else return (temp*temp)%m;
//}
// 
ll ceil(ll a, ll b){
    if (a%b) a+=b-(a%b);
    return a/b;
}
 
ll gcd(ll a, ll b){
    while (b!=0){
        ll x=a%b;
        a=b;
        b=x;
    }
    return a;
}
 
ll good_mod(ll a,ll b){
    a=a%b;
    if (a<0){
        return a+b;
    }
    else{
        return a;
    }
    
}
 
ll min(ll a, ll b){
    if (a<=b) return a;
    return b;
}
 
ll min(ll a, ll b, ll c){
    if (a<=b){
        return min(a,c);
    }
    else{
        return min(b,c);
    }
}

ll max(ll a, ll b){
    if (a>=b) return a;
    return b;
}

int sign(ll x){
    if (x==0) return 0;
    else if (x>0) return 1;
    else return -1;
}

ll bin_count(ll x){
    int c=0;
    while (x){
        x=(x&(x-1));
        c++;
    }
    return c;
}

int len_count(ll x){
    int answer=0;
    while (x){
        x>>=1;
        answer++;
    }
    return answer;
}

//int log2_floor(unsigned long i) {
//    return bit_width(i) - 1;
//}

struct Comp{
    bool operator()(const tl&a, const tl&b) const{
        return (get<2>(a) < get<2>(b));
    }
};

ll mod_exp(ll a, ll po, ll mod){
    ll mul=a;
    a=1;
    while (po){
        if (po&(1)) a*=mul;
        po=po>>1;
        mul=mul*mul;
        mul%=mod;
        a%=mod;
    }
    return a;
}

ll mod_inv(ll a, ll mod){
    return mod_exp(a,mod-2,mod);
}

struct segtree{
    int size;
    vector<ll> elements;
    void init(int n){
        size=1;
        while (size<n){
            size*=2;
        }
        
        elements=vector<ll>(2*size,LLONG_MAX);
    }

    void display(){
        for (ll i:elements)  cout<<i<<' ';
        cout<<endl;
    }

    void set(int l, int r, ll v, int pos, int lx, int rx){
        int mid=(lx+rx)/2;
        if (l<=lx && rx<=r) {
            elements[pos]=min(elements[pos],v);
            return;
        }
        
        if (l<mid  && elements[pos]>v){
            set(l,r,v,2*pos+1,lx,mid);
        }
        if (r>mid && elements[pos]>v){
            set(l,r,v,2*pos+2,mid,rx);
        }
    }
    void set(int l, int r, ll v){
        set(l,r,v,0,0,size);
    }
    
    void build(){
        for (int i=0; i<size-1; i++){
            elements[2*i+1]=min(elements[2*i+1], elements[i]);
            elements[2*i+2]=min(elements[2*i+2], elements[i]);
        }
    }
    ll get_min(int i){
        return elements[size-1+i];
    }
};

vector<int> seive(int n){
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; i++) {
        if (is_prime[i] && (long long)i * i <= n) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    vector<int> primes;
    for (int i=2; i<=n; i++){
        if (is_prime[i]) primes.pb(i);
    }
    return primes;
}

const int max_digits=19;
ll dp[max_digits+1][11][11][2][2];

string s;
int len;
void reset(){
    for (int i=0; i<=max_digits; i++){
        for (int j=0; j<11; j++){
            for (int k=0; k<11; k++){
                for (int l=0; l<2; l++){
                    dp[i][j][k][l][0]=-1;
                    dp[i][j][k][l][1]=-1;
                }
            }
        }
    }
}

ll solve(int pos, int p1, int p2, bool lead, bool eq){
    ll& state=dp[pos][p1][p2][lead][eq];
    if (state!=-1) return state;
    if (pos==len){
        state=1;
        return state;
    }
    state=0;
    int lim=9;
    if (!eq) lim=s[pos]-'0';
    
    for (int i=0; i<=lim; i++){
        if (i==p1 || i==p2) continue;
        if (lead && (i==0)) state+=solve(pos+1,p1,p2,lead&&(i==0),eq||(i<lim));
        else  state+=solve(pos+1,i,p1,lead&&(i==0),eq||(i<lim));
    }
    return state;
}
int main(){
    ll a,b;
    cin>>a>>b;
    s=to_string(b);
    len=(int)s.size();
    reset();
    ll y=solve(0,10,10,1,0);
    reset();
    s=to_string(a-1);
    len=(int)s.size();
    ll x=solve(0,10,10,1,0);
    
    cout<<y-x<<endl;
}

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