Submission #1247472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247472		clementine	Palindrome-Free Numbers (BOI13_numbers)	C++20	42.50 / 100	3 ms	524 KiB

numbers

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

template<typename T>
void _debug_cerr(const char* name, T&& value) {
    cerr << name << ": " << value << '\n';
}

template<typename T, typename... Args>
void _debug_cerr(const char* names, T&& value, Args&&... args) {
    const char* comma = strchr(names, ',');
    cerr.write(names, comma - names) << ": " << value << ", ";
    _debug_cerr(comma + 1, forward<Args>(args)...);
}

#define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__)


ll dp[10][10][20];
ll dp2[10][10][20];

void whole()
{
// base case
// l ==1
    for(int a = 0; a <=9; a ++)
    {
        for(int b = 0; b <=9; b++)
        {
            if(a != b)
            {
                dp[a][b][1] = 1;
            }
            else
            {
                dp[a][b][1] = 0;
            }
        }
    }
   
// recursion
    for(int l = 2; l <=19; l++)
    {
        for(int a = 0; a <=9; a++)
        {
            for(int b = 0; b <=9; b ++)
            {
                dp[a][b][l] = 0; // initialize
                for(int x = 0; x <=9; x ++)
                {
                    if (a !=b && a !=x && b !=x)
                        dp[a][b][l] += dp[b][x][l-1];
                }
                //if(l <=4)
                    //debug(a, b, l, dp[a][b][l]);
            }
        }
    }
}

void solve(string s)
{
    // base case l = 1
    if(s[1] != s[0])
        dp2[s[1]-'0'][s[0]-'0'][1] = 1;
    else
        dp2[s[1]-'0'][s[0]-'0'][1] = 0;
    //recursion
    for(int i = 2; i < s.length(); i ++)
    {
        
       // calculating dp2[s[i]][s[i-1]][i]
       int si = s[i] - '0';
       int si1 = s[i-1] - '0';
       int si2 = s[i-2] - '0';
       dp2[si][si1][i] = 0;
       for(int x = 0; x <s[i-2] - '0'; x ++)
       {
            if(s[i]!= s[i-1] && s[i-1] - '0' != x && s[i] - '0' != x)
            {
                dp2[si][si1][i] += dp[si1][x][i-1];
                //debug(x);
                //debug(si1, x, i-1, dp[si1][x][i-1]);
            }
       }
       if(si != si2 && si != si1)
       {
            dp2[si][si1][i] += dp2[si1][si2][i-1];
       }
       //debug(si, si1, dp2[si][si1][i]);
    }
   
}ll total(string s)
{
    ll tot = 10; // start at 10 for 0 to 9 
    int slen = s.length();
    
    for(int i = 1; i <= slen - 2; i ++)
    {
        for(int a = 1; a <=9; a ++)
        {
            for(int b = 0; b <=9; b ++)
            {
                tot += dp[a][b][i];
                //debug(a, b, i, dp[a][b][i]);
            }
        }
    }

    for(int a = 1; a < s[slen-1] - '0'; a ++)
    {
        for(int b = 0; b <=9; b ++)
        {
            tot += dp[a][b][slen-1];
            //debug(a, b, slen-1, dp[a][b][slen-1]);
        }
    }

    for(int b = 0; b < s[slen-2] - '0'; b ++)
    {
        tot += dp[s[slen-1] - '0'][b][slen-1];
        //debug(s[slen-1] - '0', b, slen - 1, dp[s[slen-1] - '0'][b][slen-1]);
    }

    debug(tot);
    return tot;
}

ll force(int a)
{
    ll temp = 0;
    for(int i = 0; i <= a; i ++)
    {
        string s = to_string(i);
       
        bool pf = true;
        for(int j = 0; j <= (int)s.length() - 2; j ++)
        {
            
            if(s[j] == s[j+1]){pf = false; break;}
        }
        for(int j = 0; j < (int)s.length() - 2; j ++)
        {
            if(s[j] == s[j+2]){pf = false; break;}
        }
        temp += pf;
    }
    return temp;
}

int main()
{
    string u, v;
    int uint;
    cin >> uint >> v;
    whole();
    ll ans =0;
    uint --;
    u = to_string(uint);
    if(stoll(v) <200)
    {
        ans = force(stoll(v));
    }
    else
    {
        reverse(v.begin(), v.end());
        //debug(v);
        solve(v); 
        int slen = v.length();
        ans = dp2[v[slen-1]- '0'][v[slen-2] - '0'][slen-1] + total(v);
        //cout << ans << '\n';   
        debug(v[slen-1]- '0', v[slen-2] - '0', slen-1, dp2[v[slen-1]- '0'][v[slen-2] - '0'][slen-1]);
        
    }
    ll ans2 = 0;
    if(uint == -1)
    {
        ans2 = 0;
    }
    else if(stoll(u) < 200)
    {
        ans2 = force(stoll(u));
    }
    else
    {
        reverse(u.begin(), u.end());
        solve(u);
        int slen2 = u.length();
        ans2 = dp2[u[slen2-1]- '0'][u[slen2-2] - '0'][slen2-1] + total(u);    
    }
    cout << ans - ans2;
}

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