Submission #1124604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124604		0pt1mus23	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	3 ms	328 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1000+23, inf = INT_MAX, LG = 20,pr = 31;

int mem[30][11][11][2][2];

int dp(int i,int balaca,int a1,int a2,int st,string s){
    if(i==s.size()){
        return 1;
    }
    if(mem[i][a1+1][a2+1][balaca][st]!=-1){
        return mem[i][a1+1][a2+1][balaca][st];
    }
    int res=0;
    int limit = (balaca?9:(s[i]-'0'));
    for(int q=0;q<=limit;q++){
        int start = (st | (q!=0));
        int bal = (balaca | (q<limit));
        if(!start){
            res+=dp(i+1,bal,a1,a2,0,s);
        }
        else{
            if(q != a1 && q!=a2){
                res+=dp(i+1,bal,a2, q,start,s);
            }
        }
    }
    
    return mem[i][a1+1][a2+1][balaca][st] = res;
}

int f(int n){
    if(n<=0){
        return 0;
    }
    string s="";

    for(int i = 20;i>=0;i--){
        if(!n){
            break;
        }
        s.pb(n%10 +'0');
        n/=10;
    }
    reverse(all(s));
    // cout<<s<<endl;

    for(int i =0;i<=23;i++){
        for(int j=0;j<=10;j++){
        for(int j1=0;j1<=10;j1++){
            for(int t=0;t<=1;t++){
                for(int st=0;st<=1;st++){
                    mem[i][j][j1][t][st]=-1;
                }
            }
        }
        }
    }

    return dp(0,0,-1,-1,0,s);
}

void fast(){
    int l,r;
    cin>>l>>r;
    if((r-l +1) <= 1e5){
        int ans=0;
        string s;
        bool flag=true;
        for(int i =l;i<=r;i++){
            s=to_string(i);
            flag=true;
            for(int j=1;j<s.size();j++){
                if(s[j]==s[j-1] || (j>1 && s[j]==s[j-2])){
                    flag=false;break; 
                }
            }
            ans+=flag;
        }
        putr(ans);
    }
    putr(f(r) - f(l-1));
}

signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

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