Submission #253416

#	Time	Username	Problem	Language	Result	Execution time	Memory
253416		tvthanh	Palindrome-Free Numbers (BOI13_numbers)	C++14	50.83 / 100	1 ms	512 KiB

numbers

#include <bits/stdc++.h>

using namespace std;
#define loop(i, a, b) for (int i = (a); i < (b); i++)
typedef long long ll;

const int MAX_DIGITS = 20;
ll cnt[MAX_DIGITS][10];
ll cnt_digits[MAX_DIGITS];
ll a, b;
ll dp[11][11][MAX_DIGITS][2];
vector<int> num;
int curr_num[MAX_DIGITS];

ll backtrack(int prev1, int prev2, int pos, int state){
    if (pos >= num.size())
        return 1;
    if(dp[prev1][prev2][pos][state] != -1)
        return dp[prev1][prev2][pos][state];
    int limit = 0;
    if(state == 0){
        limit = num[pos];
    } else
    {
        limit = 9;
    }
    ll res = 0;
    for(int i = 0; i <= limit; i++){
        int nstate = state;
        if (i < limit) nstate = 1;
        if (i != prev1 && i != prev2)
            res += backtrack(i, prev1, pos + 1, nstate);
    }
    dp[prev1][prev2][pos][state] = res;
    return dp[prev1][prev2][pos][state];
}
ll solve(int x){
    if (x < 0)
        return 0;
    num.clear();
    while(x > 0){
        num.push_back(x % 10);
        x = x / 10;
    }
    reverse(num.begin(), num.end());
    ll res = 1;
    if (num.size() == 0)
        return res;
    memset(dp, -1, sizeof(dp));
    for(int d = 1; d <= num[0]; d++){
        res += backtrack(d, d, 1, d != num[0]);
    }
    for(int k = 2; k <= num.size(); k++){
        for(int d = 1; d <= 9; d++){
            res += backtrack(d, d, k, 1);
        }
    }
    return res;
}
int main(){
    cin >> a >> b;
    cout << solve(b) - solve(a - 1) << "\n";
}

Compilation message (stderr)

numbers.cpp: In function 'll backtrack(int, int, int, int)':
numbers.cpp:16:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos >= num.size())
         ~~~~^~~~~~~~~~~~~
numbers.cpp: In function 'll solve(int)':
numbers.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = 2; k <= num.size(); k++){
                    ~~^~~~~~~~~~~~~

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