제출 #1167136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167136		InvMOD	Palindrome-Free Numbers (BOI13_numbers)	C++20	71.25 / 100	1 ms	396 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()

using ll = long long;

// dp[pos][a[pos - 2]][a[pos - 1]][tight][lead_zero]
// if it is not a palindrome then a[i] != a[i - 1] && a[i] != a[i - 2]

ll dp[20][11][11][2][2];

ll calc_dp(vector<int> num, int pos = 0, int ppre = 10, int pre = 10, bool tight = true, bool lead_zero = true){
    if(pos == sz(num)) return (!lead_zero);
    if(dp[pos][ppre][pre][tight][lead_zero] != -1) return dp[pos][ppre][pre][tight][lead_zero];

    int lb = 0, ub = (tight) ? num[pos] : 9;

    ll answer = 0;
    for(int digit = lb; digit <= ub; digit++){
        if(lead_zero && !digit){
            answer = answer + calc_dp(num, pos + 1, pre, digit, tight & (digit == ub), lead_zero & (!digit));
        }
        if(digit == pre || digit == ppre) continue;

        answer = answer + calc_dp(num, pos + 1, pre, digit, tight & (digit == ub), lead_zero & (!digit));
    }

    return dp[pos][ppre][pre][tight][lead_zero] = answer;
}

ll calc(ll x){
    if(x <= 0) return 0;

    vector<int> num;
    while(x){
        num.push_back(x % 10);
        x /= 10;
    }
    reverse(num.begin(), num.end());

    memset(dp, -1, sizeof(dp));
    return calc_dp(num);
}

void solve()
{
    ll a,b; cin >> a >> b;

    cout << calc(b) - calc(a - 1) << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

numbers.cpp: In function 'int main()':
numbers.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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