Submission #1298995

#TimeUsernameProblemLanguageResultExecution timeMemory
1298995LilPlutonPalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
2 ms588 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int inf = 12345;
const int mod = 998244353;
void opd(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}
struct BIT{
    int n;
    vector<int> ft;
    void init(int N){
        n = N;
        ft.assign(n + 1, 0);
    }
    void add(int pos, int val){
        while (pos <= n)
        {
            ft[pos] += val;
            pos += pos & -pos;
        }
    }
    int get(int pos){
        int res = 0;
        while (pos > 0)
        {
            res += ft[pos];
            pos -= pos & -pos;
        }
        return res;
    }
};

struct DSU
{
    vector<int>par, siz;
    int n;
    DSU(int N)
    {
        n = N + 5;
        par.resize(n + 1, 0);
        siz.assign(n + 1, 1);
        for(int i = 0; i <= n; ++i)
            par[i] = i;
    }
    int _find(int v)
    {
        if(par[v] == v)
            return v;
        return par[v] = _find(par[v]);
    }
    bool unite(int a, int b)
    {
        a = _find(a);
        b = _find(b);
        if(a != b)
        {
            if(siz[a] < siz[b])
                swap(a, b);
            siz[a] += siz[b];
            par[b] = a;
            return 1;
        }
        return 0;
    }
};

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

int rec(string &s, int pos,int d1,int d2,int f){
    if(pos==s.size()){
        return 1;
    }
    if(dp[pos][d1][d2][f]!=-1){
        return dp[pos][d1][d2][f];
    }
    int res=0;
    if(!d2){
        res += rec(s, pos+1, d1, d2, 0);
    }
    int st = 1 + (!d2?1:0);
    if(!f){
        for(int d3=st;d3<11;++d3){
            if(d3!=d1 && d3!=d2){
                res += rec(s, pos+1, d2, d3, 0);
            }
        }
    }
    else{
        int d=s[pos]-'0'+1;
        for(int d3=st;d3<=d;++d3){
            if(d3!=d1 && d3!=d2){
                if(d3==d){
                    res+=rec(s, pos+1, d2, d3, 1);
                }else{
                    res+=rec(s, pos+1, d2, d3, 0);
                }
            }
        }
    }
    return dp[pos][d1][d2][f]=res;
}

int calc(int a){
    if(a<0){
        return 0;
    }
    for(int i=0;i<20;++i){
        for(int j=0;j<12;++j){
            for(int k=0;k<12;++k){
                dp[i][j][k][0]=-1;
                dp[i][j][k][1]=-1;
            }
        }
    }
    string s = to_string(a);
    return rec(s, 0, 0, 0, 1);
    
}

void solve(){
    int a, b;
    cin >> a >> b;
    cout << calc(b) - calc(a-1) << endl;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //opd();
    int T = 1;
    while(T--){
        solve();
    }
    
}

Compilation message (stderr)

numbers.cpp: In function 'void opd()':
numbers.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...