oj.uz

Submission #121575

# Submission time Handle Problem Language Result Execution time Memory
121575 2019-06-26T19:27:36 Z DodgeBallMan Palindrome-Free Numbers (BOI13_numbers) C++14
23.3333 / 100
 3 ms 768 KB 
#include <bits/stdc++.h>

using namespace std;

long long a, b, dp[20][2][15][15][2];
vector<int> num;
long long solve( int pos = 0, int st1 = 0, int di1 = 10, int di2 = 10, int st2 = 0 ) {
    if( !num[pos] ) return 1LL;
    if( dp[pos][st1][di1][di2][st2] != -1 ) return dp[pos][st1][di1][di2][st2];
    if( pos >= num.size() ) return 1LL;
    int mx, ret  = 0;
    if( !st1 ) mx = num[pos];
    else mx = 9;
    for( int dgt = 0 ; dgt <= mx ; dgt++ ) {  
        if( dgt == di1 || dgt == di2 ) continue;
        int boi = st1;
        if( st1 == 0 && dgt < mx )boi = 1;
        if( !st2 && !dgt )ret += solve( pos + 1, boi, 10, 10, 0 );
        else ret += solve( pos + 1, boi, di2, dgt, 1 );
    }
    return dp[pos][st1][di1][di2][st2] = ret;
}

long long bef( long long x ) {
    num.clear();
    while( x > 0 ){
        num.emplace_back( x%10 );
        x /= 10;
    }
    reverse( num.begin(), num.end() );
    memset( dp, -1, sizeof dp );
    return solve();
}

int main()
{
    scanf("%lld %lld",&a,&b);
    printf("%lld",bef( b ) - bef( a - 1 ) );
    return 0;
}

Compilation message

numbers.cpp: In function 'long long int solve(int, int, int, int, int)':
numbers.cpp:10:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( pos >= num.size() ) return 1LL;
         ~~~~^~~~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&a,&b);
     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Correct 2 ms 512 KB Output is correct
4 Incorrect 2 ms 512 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Incorrect 2 ms 512 KB Output isn't correct
7 Incorrect 2 ms 512 KB Output isn't correct
8 Incorrect 2 ms 520 KB Output isn't correct
9 Incorrect 2 ms 384 KB Output isn't correct
10 Incorrect 2 ms 512 KB Output isn't correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Incorrect 2 ms 512 KB Output isn't correct
14 Incorrect 2 ms 512 KB Output isn't correct
15 Incorrect 2 ms 384 KB Output isn't correct
16 Incorrect 2 ms 512 KB Output isn't correct
17 Incorrect 2 ms 512 KB Output isn't correct
18 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Correct 2 ms 384 KB Output is correct
20 Incorrect 2 ms 512 KB Output isn't correct

Subtask #2
18.3333333333 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Incorrect 2 ms 512 KB Output isn't correct
4 Incorrect 2 ms 512 KB Output isn't correct
5 Incorrect 2 ms 512 KB Output isn't correct
6 Incorrect 2 ms 512 KB Output isn't correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Correct 2 ms 512 KB Output is correct
10 Incorrect 2 ms 512 KB Output isn't correct
11 Incorrect 2 ms 512 KB Output isn't correct
12 Correct 3 ms 384 KB Output is correct
13 Incorrect 2 ms 384 KB Output isn't correct
14 Incorrect 2 ms 512 KB Output isn't correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Incorrect 2 ms 384 KB Output isn't correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Incorrect 2 ms 512 KB Output isn't correct
22 Correct 2 ms 384 KB Output is correct
23 Incorrect 2 ms 384 KB Output isn't correct
24 Correct 2 ms 384 KB Output is correct
25 Incorrect 2 ms 512 KB Output isn't correct
26 Incorrect 2 ms 384 KB Output isn't correct
27 Incorrect 2 ms 512 KB Output isn't correct
28 Incorrect 2 ms 512 KB Output isn't correct
29 Correct 2 ms 512 KB Output is correct
30 Incorrect 3 ms 512 KB Output isn't correct
31 Incorrect 2 ms 384 KB Output isn't correct
32 Incorrect 2 ms 384 KB Output isn't correct
33 Incorrect 2 ms 512 KB Output isn't correct
34 Incorrect 2 ms 512 KB Output isn't correct
35 Incorrect 2 ms 384 KB Output isn't correct
36 Incorrect 2 ms 512 KB Output isn't correct
37 Incorrect 2 ms 384 KB Output isn't correct
38 Incorrect 2 ms 512 KB Output isn't correct
39 Incorrect 2 ms 384 KB Output isn't correct
40 Incorrect 3 ms 512 KB Output isn't correct
41 Incorrect 2 ms 512 KB Output isn't correct
42 Incorrect 2 ms 512 KB Output isn't correct
43 Incorrect 2 ms 512 KB Output isn't correct
44 Incorrect 2 ms 512 KB Output isn't correct
45 Incorrect 2 ms 384 KB Output isn't correct