Submission #137506

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137506	2019-07-28T05:43:42 Z	silxikys	Palindrome-Free Numbers (BOI13_numbers)	C++14	37.5 / 100	3 ms	504 KB

numbers

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

int dig[20];
ll dp[20][11][11][2]; //place, 2, 1, isover

int f(int len, int d1, int d2, bool under) {
    if (len == -1) return 1;
    ll& res = dp[len][d1][d2][under];
    if (res >= 0) return res;
    if (under) {
        res = 0;
        for (int d = 0; d <= 9; d++) {
            if (d == d1 || d == d2) continue;
            res += f(len-1,d2,d,under);
        }
        return res;
    }
    else {
        res = 0;
        for (int d = 0; d < dig[len]; d++) {
            if (d == d1 || d == d2) continue;
            res += f(len-1,d2,d,true);
        }
        if (dig[len] != d1 && dig[len] != d2) 
            res += f(len-1,d2,dig[len],under);
        return res;
    }
}

ll solve(ll x) {
    if (x == -1) return 0;
    memset(dp,-1,sizeof dp);
    int len = 0;
    while (x) {
        dig[len++] = x % 10;
        x /= 10;
    }
    return f(len-1,10,10,0);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll a, b; cin >> a >> b;
    cout << (solve(b) - solve(a-1)) << '\n';
    //cout << solve(a) << '\n';
}

Subtask #1

12.5 / 25.0

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

Subtask #2

25.0 / 75.0

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