Submission #790542

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790542	2023-07-22T20:18:58 Z	tch1cherin	Palindrome-Free Numbers (BOI13_numbers)	C++17	73.75 / 100	1 ms	384 KB

numbers

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

const int MAX_N = 26;
int64_t DP[MAX_N][11][11];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int64_t l, r;
  cin >> l >> r;
  r++;
  string _L = to_string(l), _R = to_string(r);
  reverse(_L.begin(), _L.end());
  reverse(_R.begin(), _R.end());
  while (_L.size() < MAX_N - 1) {
    _L += '0' + 10;
  }
  while (_R.size() < MAX_N - 1) {
    _R += '0' + 10;
  }
  reverse(_L.begin(), _L.end());
  reverse(_R.begin(), _R.end());
  auto Count = [](string R) {
    memset(DP, 0, sizeof DP);
    bool good = true;
    for (int i = 2; i < MAX_N - 1; i++) {
      if ((R[i - 1] != '0' + 10) && (R[i - 1] == R[i - 2] || (i >= 3 && R[i - 1] == R[i - 3]))) {
        good = false;
      }
      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 (R[i] != '0' + 10 && C < R[i] - '0' && A == R[i - 2] - '0' && B == R[i - 1] - '0' && good) {
              DP[i + 1][B][A == 10 && B == 10 && C == 0 ? 10 : C]++;
            }
            DP[i + 1][B][C] += DP[i][A][B]; 
          }
        }
      }
    }
    int64_t ans = 0;
    for (int A = 0; A <= 10; A++) {
      for (int B = 0; B <= 10; B++) {
        ans += DP[MAX_N - 1][A][B];
      }
    }
    return ans;
  };
  cout << Count(_R) - Count(_L) << "\n";
}

Subtask #1

13.75 / 25.0

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

Subtask #2

60.0 / 75.0

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