답안 #438270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438270	2021-06-27T19:56:13 Z	SirCovidThe19th	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	296 KB

numbers

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define FOR(i, x, y) for (int i = x; i < y; i++)

ll pw[19];

ll solve(ll val){
    ll dp[2][2][10][10][2] = {}, ans = 0; 
    FOR(i, 0, 10) FOR(j, 0, 10) if (i != j or (i == 0 and j == 0)){
        dp[1][(i*10+j <= val%100) ? 0 : 1][i][j][0]++;
    }FOR(i, 2, 19){
        memset(dp[0], 0, sizeof(dp[0])); ll dig = (val/pw[i])%10;
        FOR(cmp, 0, 2) FOR(n1, 0, 10) FOR(n2, 0, 10) FOR(n3, 0, 2) FOR(j, 0, 10){
            ll CMP = cmp; if (j < dig){CMP = 0;} if (j > dig){CMP = 1;}
            if (j == 0 or (j != n1 and j != n2 and n1 != n2 and !(n3 == 1 and n1 == 0)))
                dp[0][CMP][j][n1][(n2 == 0)] += dp[1][cmp][n1][n2][n3];
        }swap(dp[0], dp[1]);
    }FOR(i, 0, 10) FOR(j, 0, 10) FOR(k, 0, 2) ans += dp[1][0][i][j][k];
    return ans;
}
int main(){
    ll a, b; cin >> a >> b; pw[0] = 1; FOR(i, 1, 19) pw[i] = pw[i-1]*10;
    cout<<solve(b)-solve(a-1);
}

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	2 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	288 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	288 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	2 ms	204 KB	Output is correct
16	Correct	1 ms	288 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct

Subtask #2

75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	2 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	288 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	2 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	2 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	2 ms	204 KB	Output is correct
23	Correct	1 ms	292 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	296 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	2 ms	204 KB	Output is correct
28	Correct	1 ms	204 KB	Output is correct
29	Correct	2 ms	204 KB	Output is correct
30	Correct	1 ms	288 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	1 ms	204 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct
34	Correct	1 ms	204 KB	Output is correct
35	Correct	1 ms	204 KB	Output is correct
36	Correct	1 ms	204 KB	Output is correct
37	Correct	2 ms	204 KB	Output is correct
38	Correct	1 ms	204 KB	Output is correct
39	Correct	1 ms	204 KB	Output is correct
40	Correct	1 ms	292 KB	Output is correct
41	Correct	1 ms	204 KB	Output is correct
42	Correct	1 ms	204 KB	Output is correct
43	Correct	1 ms	204 KB	Output is correct
44	Correct	1 ms	288 KB	Output is correct
45	Correct	1 ms	204 KB	Output is correct