Submission #538689

#	Time	Username	Problem	Language	Result	Execution time	Memory
538689		Lobo	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	468 KiB

numbers

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

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 20

ii n, a[maxn], b[maxn], mark[maxn][11][11][2][2][2];
ll dp[maxn][11][11][2][2][2];

ll sol(ii i, ii ant, ii act, ii pa, ii pb, ii zr) {
    if(i == n+1) return 1;

    if(mark[i][ant][act][pa][pb][zr]) return dp[i][ant][act][pa][pb][zr];

    mark[i][ant][act][pa][pb][zr] = 1;

    ll ans = 0;

    if(zr == 1 && a[i] == 0) {
        ans+= sol(i+1,10,10,0,1,1);
    }

    for(ii j = 0; j <= 9; j++) {
        if(zr == 1 && j == 0) continue;

        if(j == ant || j == act || (pa == 0 && j < a[i]) || (pb == 0 && j > b[i])) continue;
        ii npa = pa;
        if((a[i] != -1 && j > a[i]) || (a[i] == -1 && j > 0)) npa = 1;

        ii npb = pb;
        if(j < b[i]) npb = 1;

        ans+= sol(i+1,act,j,npa,npb,0);
    }

    //cout << i << " " << ant << " " << act << " " << pa << " " << pb << " " << zr << " == " << ans << endl;

    return dp[i][ant][act][pa][pb][zr] = ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    string sa,sb;
    cin >> sa >> sb;
    n = sb.size();
    reverse(all(sa));
    while(sa.size() < sb.size()) {
        sa+= '0';
    }
    reverse(all(sa));

    for(ii i = 1; i <= sb.size(); i++) {
        b[i] = sb[i-1]-'0';
    }

    for(ii i = 1; i <= sa.size(); i++) {
        a[i] = sa[i-1]-'0';
    }
    

    cout << sol(1,10,10,0,0,1) << endl;

}

Compilation message (stderr)

numbers.cpp: In function 'int main()':
numbers.cpp:68:21: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(ii i = 1; i <= sb.size(); i++) {
      |                   ~~^~~~~~~~~~~~
numbers.cpp:72:21: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(ii i = 1; i <= sa.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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