Submission #78384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
78384	2018-10-04T14:05:59 Z	HellAngel	Palindrome-Free Numbers (BOI13_numbers)	C++14	73.75 / 100	3 ms	916 KB

numbers

#include <bits/stdc++.h>
#define int long long

using namespace std;
string s;
int a, b;

int dp[21][2][2][11][11];

string Convert(int a)
{
    string s;
    if(a == 0) return "0";
    while(a > 0)
    {
        s += a % 10 + '0';
        a /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}

int DP(int pos, bool prefix, bool allz, int last2, int last1)
{
    if(~dp[pos][prefix][allz][last1][last2]) return dp[pos][prefix][allz][last1][last2];
    if(pos == s.length()) return 1;
    int limit;
    if(prefix) limit = s[pos] - '0';
    else limit = 9;
    int ans = 0;
    for(int d = 0; d <= limit; d++)
    {
        int digit;
        if(d == 0 && allz) digit = 10;
        else digit = d;
        if(digit != 10 && digit == last1) continue;
        if(digit != 10 && digit == last2) continue;
        ans += DP(pos + 1, prefix && d == limit, allz && d == 0, last1, d);
    }
    return dp[pos][prefix][allz][last1][last2] = ans;
}

int Get()
{
    fill_n(&dp[0][0][0][0][0], 21 * 2 * 2 * 11 * 11, -1);
    return DP(0, 1, 1, 10, 10);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> a >> b;
    s = Convert(a - 1);
    int ans1 = Get();
    s = Convert(b);
    int ans2 = Get();
    if(a == 0) cout << ans2;
    else
    cout << ans2 - ans1;
}

Compilation message

numbers.cpp: In function 'long long int DP(long long int, bool, bool, long long int, long long int)':
numbers.cpp:26:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos == s.length()) return 1;
        ~~~~^~~~~~~~~~~~~

Subtask #1

13.75 / 25.0

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

Subtask #2

60.0 / 75.0

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