Submission #99524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
99524	2019-03-04T17:11:00 Z	MohamedAhmed0	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	5 ms	512 KB

numbers

#include <bits/stdc++.h>

using namespace std;

long long dp[19][2][2][11][11] ;
vector<int>v ;

long long cnt(int idx , bool f , bool f2 , int prv , int prv2)
{
    if(idx == v.size())
        return 1 ;
    long long &ret = dp[idx][f][f2][prv][prv2] ;
    if(ret != -1)
        return ret ;
    int LMT ;
    if(f)
        LMT = 9 ;
    else
        LMT = v[idx] ;
    ret = 0ll ;
    for(int i = 0 ; i <= LMT ; ++i)
    {
        int nf = f ;
        int nf2 = f2 ;
        if(i < LMT)
            nf = 1 ;
        if(i == prv || i == prv2)
            continue;
        if(i != 0)
            nf2 = 1 ;
        if(nf2 == 0)
            ret += cnt(idx+1 , nf , nf2 , 10 , 10) ;
        else
            ret += cnt(idx+1 , nf , nf2 , i , prv) ;
    }
    return ret ;
}
long long solve(long long x)
{
    if(x < 0)
        return 0 ;
    v.clear();
    memset(dp , -1 , sizeof(dp)) ;
    while(x > 0)
    {
        v.push_back(x % 10) ;
        x /= 10 ;
    }
    reverse(v.begin() , v.end()) ;
    long long ans = cnt(0 , 0 , 0 , 10 , 10) ;
    return ans ;
}

int main()
{
    long long a , b ;
    cin>>a>>b ;
    return cout<<solve(b) - solve(a-1)<<"\n" , 0 ;
}

Compilation message

numbers.cpp: In function 'long long int cnt(int, bool, bool, int, int)':
numbers.cpp:10:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(idx == v.size())
        ~~~~^~~~~~~~~~~

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	3 ms	380 KB	Output is correct

Subtask #2

75.0 / 75.0

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