Submission #950464

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
950464	2024-03-20T10:32:17 Z	phoenix0423	Palindrome-Free Numbers (BOI13_numbers)	C++17	96.25 / 100	2 ms	544 KB

numbers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long 
const int maxn = 1e5 + 5;

int sol(int x){
    if(x < 0) return 0;
    string s = to_string(x);
    vector<vector<vector<int>>> dp(11, vector<vector<int>>(11, vector<int>(2)));
    dp[10][10][1] = 1;
    int n = s.size();
    for(int i = 0; i < n; i++){
        vector<vector<vector<int>>> ndp(11, vector<vector<int>>(11, vector<int>(2)));
        for(int a = 0; a <= 10; a++){
            for(int b = 0; b <= 10; b++){
                for(int c = 0; c < 10; c++){
                    if(a == c || b == c) continue;
                    if(a == 10 && b == 10 && c == 0) continue;
                    if(c < s[i] - '0'){
                        ndp[b][c][0] += dp[a][b][0] + dp[a][b][1];
                    }
                    else if(c == s[i] - '0'){
                        ndp[b][c][0] += dp[a][b][0], ndp[b][c][1] += dp[a][b][1];
                    }
                    else{
                        ndp[b][c][0] += dp[a][b][0];
                    }
                }
            }
        }
        ndp[10][10][0] = 1;
        swap(dp, ndp);
    }
    int ret = 0;
    for(int i = 0; i <= 10; i++){
        for(int j = 0; j < 10; j++){
            for(int k = 0; k < 2; k++) ret += dp[i][j][k];
        }
    }
    return ret;
}
signed main(void){
    int a, b;
    cin>>a>>b;
    cout<<sol(b) - sol(a - 1)<<"\n";
}

Subtask #1

21.25 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	436 KB	Output is correct
14	Incorrect	1 ms	348 KB	Output isn't correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct

Subtask #2

75.0 / 75.0

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