Submission #624856

#	Time	Username	Problem	Language	Result	Execution time	Memory
624856		chonka	Palindrome-Free Numbers (BOI13_numbers)	C++17	96.25 / 100	1 ms	340 KiB

numbers

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vector < int > v ;

ll dp[ 22 ][ 123 ][ 2 ] ;

ll f ( ll up ) {
    v.clear ( ) ;
    while ( up > 0 ) {
        v.push_back ( up % 10 ) ;
        up /= 10 ;
    }
    reverse ( v.begin ( ) , v.end ( ) ) ;
    int n = v.size ( ) ;
    for ( int i = 0 ; i <= n ; ++ i ) {
        for ( int j = 0 ; j <= 121 ; ++ j ) {
            for ( int t = 0 ; t < 2 ; ++ t ) {
                dp[ i ][ j ][ t ] = 0 ;
            }
        }
    }
    dp[ 0 ][ 120 ][ 1 ] = 1 ;
    for ( int i = 0 ; i < n ; ++ i ) {
        for ( int j = 0 ; j <= 120 ; ++ j ) {
            int x = ( j / 11 ) , y = ( j % 11 ) ;
            for ( int t = 0 ; t < 2 ; ++ t ) {
                if ( dp[ i ][ j ][ t ] == 0 ) { continue ; }
                for ( int z = 0 ; z <= 10 ; ++ z ) {
                    if ( z == 10 ) {
                        if ( y != 10 ) { continue ; }
                        dp[ i + 1 ][ j ][ 0 ] += dp[ i ][ j ][ t ] ;
                    }
                    else {
                        if ( z == 0 && y == 10 ) { continue ; }
                        if ( t == 1 && z > v[ i ] ) { continue ; }
                        int nwt = t ;
                        if ( z < v[ i ] ) { nwt = 0 ; }

                        if ( z == x || z == y ) { continue ; }
                        int nwj = z + 11 * y ;
                        dp[ i + 1 ][ nwj ][ nwt ] += dp[ i ][ j ][ t ] ;
                    }
                }
            }
        }
    }
    ll ret = 0 ;
    for ( int i = 0 ; i <= 120 ; ++ i ) {
        ret += dp[ n ][ i ][ 0 ] + dp[ n ][ i ][ 1 ] ;
    }
    return ret ;
}

void solve ( ) {
    ll l , r ;
    cin >> l >> r ;
    cout << f ( r ) - f ( l - 1 ) << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

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