Submission #283065

#	Time	Username	Problem	Language	Result	Execution time	Memory
283065		Atill83	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	11 ms	512 KiB

numbers

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll d[2][13][12][11];
int bas[21];
ll kc[20];

bool pal(ll a){
    ll last1 = -2, last2 = -1;

    while(a){
        ll cur = a % 10;
        if(cur == last1 || cur == last2){
            return 0;
        }
        last1 = last2;
        last2 = cur;
        a /= 10;
    }
    return 1;
}

ll ite(int say){
    ll ans = 0;
    if(say == 0){
        for(int j = 0; j <= 11; j++){
            for(int k = 0; k <= 10; k++){
                for(int l = 0; l <= 9; l++){
                    if(k == 10 && l == 0) continue;
                    ans += d[0][j][k][l];
                }
            }
        }
    }
    for(int i = 1; i <= say; i++){
        ans = 0;
        memset(d[i&1], 0, sizeof(d[i&1]));
        for(int j = 0; j <= 11; j++){
            for(int k = 0; k <= 10; k++){
                for(int l = 0; l <= 9; l++){
                    if(l == 0 && k == 10) continue;
                    if(j == k || k == l || j == l) continue;
                    for(int z = 0; z <= 12; z++){
                        if(z == j || z == k || j == k) continue;
                        d[i&1][j][k][l] += d[i&1^1][z][j][k];
                    }
                    ans += d[i&1][j][k][l];
                }
            }
        }
    }
    return ans;
}



ll cn(ll x){
    if(x < 0) return 0;
    if(x <= 9) return x + 1;
    ll y = x;
    int idx = 0;
    while(y){
        bas[idx++] = y % 10;
        y /= 10;
    }
    reverse(bas, bas + idx);
    ll ans = 0;
    for(int i = 1; i < idx; i++){
        ans += kc[i];
    }
    ll cur = 0;
    //cerr<<x<<" "<<idx<<endl;
    for(int i = 0; i < idx; i++){
        if(pal(cur)){
            memset(d[0], 0, sizeof(d[0]));
            if(i == 0){
                for(int j = 1; j < bas[i]; j++){
                    d[0][11][10][j] = 1;
                }
                ans += ite(idx - (i + 1));
            }else if(i == 1){
                for(int j = 0; j < bas[i]; j++){
                    if(j == bas[i - 1]) continue;
                    d[0][10][bas[i - 1]][j] = 1;
                }
                ans += ite(idx - (i + 1));
            }else{
                
                for(int j = 0; j < bas[i]; j++){
                    if(j == bas[i - 1] || j == bas[i - 2]) continue;
                    d[0][bas[i - 2]][bas[i - 1]][j] = 1;
                }
                ans += ite(idx - (i + 1));
            }
        }else{
            break;
        }
        cur *= 10;
        cur += bas[i];
    }
    //cerr<<x<<" "<<ans<<endl;
    ans += pal(x);
    return ans;
}




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif
    ll a, b;
    cin>>a>>b;


    d[0][12][11][10] = 1;


    for(int i = 1; i <= 19; i++){
        memset(d[i&1], 0, sizeof(d[i&1]));
        for(int j = 0; j <= 11; j++){
            for(int k = 0; k <= 10; k++){
                for(int l = 0; l <= 9; l++){
                    if(l == 0 && k == 10) continue;
                    if(j == k || k == l || j == l) continue;
                    for(int z = 0; z <= 12; z++){
                        if(z == j || z == k || j == k) continue;
                        d[i&1][j][k][l] += d[i&1^1][z][j][k];
                    }
                    kc[i] += d[i&1][j][k][l];
                }
            }
        }
    }
    kc[1]++;
    cout<<cn(b) - cn(a - 1)<<endl;  




    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

numbers.cpp: In function 'll ite(int)':
numbers.cpp:55:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   55 |                         d[i&1][j][k][l] += d[i&1^1][z][j][k];
      |                                              ~^~
numbers.cpp: In function 'int main()':
numbers.cpp:143:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  143 |                         d[i&1][j][k][l] += d[i&1^1][z][j][k];
      |                                              ~^~

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