제출 #1255132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255132		Mer123haba456	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	0 ms	328 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define N lli(2e5)
#define MOD lli(1e9 + 7)
#define heps(v) v.begin(), v.end()
typedef long long int lli;
typedef vector<lli> vlli;
typedef pair<lli, lli> plli;
typedef vector<plli> vplli;
typedef pair<lli, plli> pplli;
typedef vector<pplli> vpplli;

lli n,m,k,q,t;

lli dp[N];
lli hepsek[N];

bool ispal(lli say){
    vlli vect;
    while(say > 0 ){
        vect.push_back(say%10);
        say/=10;
    }
    bool durum = 1;
    for(lli i = 0;i<vect.size();i++){
        if(i > 0 && vect[i] == vect[i-1])
            durum = 0;
        if(i > 1 && vect[i] == vect[i-2])
            durum = 0;
    }
    return durum;
}

lli palbul(lli say){
    vlli vect;
    while(say > 0){
        vect.push_back(say % 10);
        say/=10;
    }
    lli dond = 0;
    for(lli i = 0;i<vect.size();i++){
        if(i == 0)
            dond += 1;
        else if(i == 1)
            dond += 9;
        else
            dond += 9 * 9 * dp[i-2];
    }
    //cout << "bas" << dond << endl;
    for(lli i = vect.size()-1;i>=0;i--){
        if(vect[i] > 0){
            if(i + 1 < vect.size()){
                lli kacart = vect[i];
                if(i + 1 < vect.size() && vect[i + 1] < vect[i])
                    kacart--;
                if(i + 2 < vect.size() && vect[i + 2] < vect[i])
                    kacart--;
                dond += kacart * dp[i];
            }else{
                if(i == 0)
                    dond += vect[i] - 1;
                else
                    dond += (vect[i] - 1) * 9 * dp[i-1];
            }
            //cout << i << " " << dond << endl;
        }
        
        if(i + 1 < vect.size() && vect[i] == vect[i+1])
            break;
        if(i + 2 < vect.size() && vect[i] == vect[i+2])
            break;
        if(i == 0)
            dond++;
    }
    if(vect.empty())
        return 1;
    return dond;
}

int main()
{
    fast_io
    cin >> n >> m;
    dp[0] = 1;
    for(lli i = 1;i<=19;i++){
        dp[i] = dp[i-1] * 8;
    }
    lli msu = palbul(m);
    lli say = 0;
    /*for(lli i = 0;i<=m;i++)
        say += ispal(i);
    cout << msu << " " << say << endl;*/
    if(n == 0)
        cout << msu << endl;
    else
        cout << msu - palbul(n-1) << endl;
}

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