제출 #438270

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

numbers

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define FOR(i, x, y) for (int i = x; i < y; i++)

ll pw[19];

ll solve(ll val){
    ll dp[2][2][10][10][2] = {}, ans = 0; 
    FOR(i, 0, 10) FOR(j, 0, 10) if (i != j or (i == 0 and j == 0)){
        dp[1][(i*10+j <= val%100) ? 0 : 1][i][j][0]++;
    }FOR(i, 2, 19){
        memset(dp[0], 0, sizeof(dp[0])); ll dig = (val/pw[i])%10;
        FOR(cmp, 0, 2) FOR(n1, 0, 10) FOR(n2, 0, 10) FOR(n3, 0, 2) FOR(j, 0, 10){
            ll CMP = cmp; if (j < dig){CMP = 0;} if (j > dig){CMP = 1;}
            if (j == 0 or (j != n1 and j != n2 and n1 != n2 and !(n3 == 1 and n1 == 0)))
                dp[0][CMP][j][n1][(n2 == 0)] += dp[1][cmp][n1][n2][n3];
        }swap(dp[0], dp[1]);
    }FOR(i, 0, 10) FOR(j, 0, 10) FOR(k, 0, 2) ans += dp[1][0][i][j][k];
    return ans;
}
int main(){
    ll a, b; cin >> a >> b; pw[0] = 1; FOR(i, 1, 19) pw[i] = pw[i-1]*10;
    cout<<solve(b)-solve(a-1);
}

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