Submission #240587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
240587	2020-06-20T07:19:23 Z	nafis_shifat	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	6 ms	384 KB

numbers

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[19][11][11][2]={};
int len;
int ar[19];

ll DP(int pos,int m1,int m2,int sm) {
    
    ll &ret=dp[pos][m1+1][m2+1][sm];
    if(len==pos) {
        ret=1;
        return 1;
    }
    if(ret!=-1)return ret;
    ret=0;
    int mx=sm?9:ar[pos];
    for(int i=0;i<mx;i++) {
        if(i!=m1&&i!=m2)
            ret+=DP(pos+1,m2,i,1);
    }
    if(mx!=m2 && mx!=m1)
        ret+=DP(pos+1,m2,mx,sm);
    return ret;
    
}


ll calc(ll a) {
    if(a<=9)return a+1;
    memset(dp,-1,sizeof dp);
    len=0;
    while(a) {
        ar[len++]=a%10;
        a/=10;
    }
    reverse(ar,ar+len);
    ll res=DP(0,0,-1,0);
    for(int i=1;i<=len;i++)res+=DP(i,0,-1,1);
    return res;
    
}
int main() {
    ll a,b;
    cin>>a>>b;
    if(a<b)
        swap(a,b);
        
    ll pd=calc(a)-calc(b-1);
    cout<<pd<<endl;
}

Subtask #1

25.0 / 25.0

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

Subtask #2

75.0 / 75.0

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