oj.uz

Submission #528327

# Submission time Handle Problem Language Result Execution time Memory
528327 2022-02-20T03:10:59 Z CherryMagic Palindrome-Free Numbers (BOI13_numbers) C++14
0 / 100
 1000 ms 2404 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

long a,b;
long dp[25][10][10][2][2][25];
vector<int> num;

long call(int pos, int dig1, int dig2, int notpal, int f, int nz){
    if (pos == num.size()){
        if (notpal) return 1;
        return 0;
    }
    if (dp[pos][dig1][dig2][notpal][f][nz] != -1)
        return dp[pos][dig1][dig2][notpal][f][nz];
    long res = 0;
    int lmt;
    if (f == 0){
        lmt = num[pos];
    }
    else lmt = 9;
    for (int dgt=0;dgt<=lmt;dgt++){
        int ndig1, ndig2, nnotpal=notpal, nf=f, nnz=nz;
        if (f == 0 && dgt < lmt ) nf=1;
        if (nz<=pos) nnz = nz;
        else{
            if (dgt != 0) nnz = pos+1;
            else nnz = 23;
        }
        if ((pos>=3 && dgt==dig2 && pos>=nz)||
            (pos>=4 && dgt==dig1 && pos>=nz+1)) nnotpal=0;
        ndig1 = dig2;
        ndig2 = dgt;

        if (nnotpal) res+= call(pos+1, ndig1, ndig2, nnotpal, nf, nnz);
    }
    return dp[pos][dig1][dig2][notpal][f][nz]= res;
}

long solve(int a){
    num.clear();
    while (a > 0){
        num.push_back(a%10);
        a/=10;
    }
    num.push_back(0);
    num.push_back(0);
    reverse(num.begin(), num.end());
    memset(dp, -1, sizeof(dp));
    return call(2, 0, 0, 1, 0, 23);
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        cin >> a >> b;
        if (a == 0) cout<<solve(b)<<endl;
        else cout << solve(b) - solve(a-1);
    }
    return 0;
}

Compilation message

numbers.cpp: In function 'long int call(int, int, int, int, int, int)':
numbers.cpp:13:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if (pos == num.size()){
      |         ~~~~^~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2124 KB Output isn't correct
2 Incorrect 1 ms 2124 KB Output isn't correct
3 Execution timed out 1075 ms 2384 KB Time limit exceeded
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 1 ms 2124 KB Output isn't correct
6 Incorrect 1 ms 2124 KB Output isn't correct
7 Incorrect 1 ms 2124 KB Output isn't correct
8 Incorrect 2 ms 2124 KB Output isn't correct
9 Incorrect 6 ms 2124 KB Output isn't correct
10 Incorrect 40 ms 2124 KB Output isn't correct
11 Execution timed out 1054 ms 2248 KB Time limit exceeded
12 Execution timed out 1085 ms 2372 KB Time limit exceeded
13 Incorrect 11 ms 2124 KB Output isn't correct
14 Incorrect 0 ms 204 KB Output isn't correct
15 Incorrect 1 ms 2252 KB Output isn't correct
16 Execution timed out 1096 ms 2256 KB Time limit exceeded
17 Execution timed out 1089 ms 2376 KB Time limit exceeded
18 Incorrect 0 ms 204 KB Output isn't correct
19 Execution timed out 1084 ms 2376 KB Time limit exceeded
20 Incorrect 3 ms 2124 KB Output isn't correct

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 2240 KB Time limit exceeded
2 Execution timed out 1066 ms 2260 KB Time limit exceeded
3 Execution timed out 1089 ms 2384 KB Time limit exceeded
4 Execution timed out 1086 ms 2388 KB Time limit exceeded
5 Execution timed out 1089 ms 2244 KB Time limit exceeded
6 Execution timed out 1082 ms 2248 KB Time limit exceeded
7 Execution timed out 1094 ms 2248 KB Time limit exceeded
8 Execution timed out 1097 ms 2352 KB Time limit exceeded
9 Incorrect 35 ms 2124 KB Output isn't correct
10 Execution timed out 1095 ms 2368 KB Time limit exceeded
11 Execution timed out 1067 ms 2244 KB Time limit exceeded
12 Execution timed out 1098 ms 2356 KB Time limit exceeded
13 Execution timed out 1090 ms 2240 KB Time limit exceeded
14 Execution timed out 1088 ms 2364 KB Time limit exceeded
15 Incorrect 533 ms 2240 KB Output isn't correct
16 Execution timed out 1082 ms 2260 KB Time limit exceeded
17 Execution timed out 1087 ms 2268 KB Time limit exceeded
18 Execution timed out 1078 ms 2260 KB Time limit exceeded
19 Execution timed out 1090 ms 2372 KB Time limit exceeded
20 Execution timed out 1067 ms 2268 KB Time limit exceeded
21 Execution timed out 1082 ms 2396 KB Time limit exceeded
22 Execution timed out 1090 ms 2380 KB Time limit exceeded
23 Execution timed out 1093 ms 2372 KB Time limit exceeded
24 Execution timed out 1091 ms 2248 KB Time limit exceeded
25 Execution timed out 1087 ms 2264 KB Time limit exceeded
26 Execution timed out 1077 ms 2380 KB Time limit exceeded
27 Execution timed out 1088 ms 2272 KB Time limit exceeded
28 Execution timed out 1091 ms 2256 KB Time limit exceeded
29 Execution timed out 1099 ms 2272 KB Time limit exceeded
30 Execution timed out 1092 ms 2248 KB Time limit exceeded
31 Execution timed out 1075 ms 2280 KB Time limit exceeded
32 Execution timed out 1090 ms 2236 KB Time limit exceeded
33 Execution timed out 1094 ms 2260 KB Time limit exceeded
34 Execution timed out 1088 ms 2260 KB Time limit exceeded
35 Execution timed out 1097 ms 2364 KB Time limit exceeded
36 Execution timed out 1086 ms 2280 KB Time limit exceeded
37 Execution timed out 1098 ms 2388 KB Time limit exceeded
38 Execution timed out 1090 ms 2404 KB Time limit exceeded
39 Execution timed out 1092 ms 2376 KB Time limit exceeded
40 Execution timed out 1090 ms 2372 KB Time limit exceeded
41 Execution timed out 1089 ms 2252 KB Time limit exceeded
42 Execution timed out 1090 ms 2276 KB Time limit exceeded
43 Execution timed out 1091 ms 2384 KB Time limit exceeded
44 Execution timed out 1099 ms 2268 KB Time limit exceeded
45 Execution timed out 1099 ms 2268 KB Time limit exceeded