oj.uz

Submission #584146

# Submission time Handle Problem Language Result Execution time Memory
584146 2022-06-27T00:03:30 Z Olympia Palindrome-Free Numbers (BOI13_numbers) C++17
15 / 100
 22 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome (int64_t i) {
    string s = to_string(i);
    bool fine = true;
    for (int j = 0; j < s.length(); j++) {
        if (j >= 1 && s[j] == s[j - 1]) {
            fine = false;
        }
        if (j >= 2 && s[j] == s[j - 2]) {
            fine = false;
        }
    }
    return fine;
}
int64_t powerOf10 (int x) {
    //pow(10, x)
    if (x == 1) {
        return 10;
    }
    int64_t tot = 81;
    for (int i = 0; i < x - 2; i++) {
        tot *= 8;
    }
    return tot + powerOf10(x - 1);
}
int64_t res (int64_t a, int64_t b) {
    int64_t ans = 0;
    for (int64_t i = a; i <= b; i++) {
        ans += isPalindrome(i);
    }
    return ans;
}
int64_t removeAllBut2 (int64_t x) {
    string s = to_string(x);
    for (int i = 2; i < s.length(); i++) {
        s[i] = '0';
    }
    return stoll(s);
}
int64_t query (int64_t a, int64_t b) {
    if (b - a <= 1000) {
        return res(a, b);
    }
    if (a != 0) {
        return query(0, b) - query(0, a - 1);
    }
    if (a == b) {
        return a;
    }
    string s = to_string(b);
    int64_t tot = 0;
    int64_t c = 0;
    for (int i = 1; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                if (i == j || j == k || i == k) continue;
                c += (100 * i + 10 * j + k <= 100 * (s[0] - '0') + 10 * (s[1] - '0') + (s[2] - '0'));
            }
        }
    }
    tot += c * pow(8ll, (int)s.size() - 3);
    tot += powerOf10((int)s.length() - 1);
    reverse(s.begin(), s.end());
    s.pop_back();
    reverse(s.begin(), s.end());
    b = stoll(s);
    tot += query(removeAllBut2(b), b);
    if (tot != res(a, b)) {
        cout << a << " " << b << '\n';
        assert(false);
    }
    return tot;
}
int main() {
    int64_t a, b;
    cin >> a >> b;
    cout << query(a, b) << '\n';
}

Compilation message

numbers.cpp: In function 'bool isPalindrome(int64_t)':
numbers.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (int j = 0; j < s.length(); j++) {
      |                     ~~^~~~~~~~~~~~
numbers.cpp: In function 'int64_t removeAllBut2(int64_t)':
numbers.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 2; i < s.length(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
15.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 2 ms 468 KB Execution killed with signal 6
4 Runtime error 1 ms 340 KB Execution killed with signal 6
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Runtime error 1 ms 412 KB Execution killed with signal 6
15 Runtime error 1 ms 468 KB Execution killed with signal 6
16 Runtime error 1 ms 340 KB Execution killed with signal 6
17 Runtime error 2 ms 424 KB Execution killed with signal 6
18 Correct 0 ms 212 KB Output is correct
19 Runtime error 1 ms 340 KB Execution killed with signal 6
20 Runtime error 1 ms 340 KB Execution killed with signal 6

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 340 KB Execution killed with signal 6
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Runtime error 2 ms 468 KB Execution killed with signal 6
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Runtime error 2 ms 468 KB Execution killed with signal 6
7 Runtime error 2 ms 468 KB Execution killed with signal 6
8 Runtime error 2 ms 420 KB Execution killed with signal 6
9 Runtime error 2 ms 468 KB Execution killed with signal 6
10 Runtime error 2 ms 340 KB Execution killed with signal 6
11 Runtime error 2 ms 340 KB Execution killed with signal 6
12 Runtime error 2 ms 468 KB Execution killed with signal 6
13 Runtime error 2 ms 468 KB Execution killed with signal 6
14 Runtime error 1 ms 340 KB Execution killed with signal 6
15 Runtime error 1 ms 468 KB Execution killed with signal 6
16 Runtime error 1 ms 468 KB Execution killed with signal 6
17 Runtime error 2 ms 468 KB Execution killed with signal 6
18 Runtime error 2 ms 468 KB Execution killed with signal 6
19 Runtime error 3 ms 468 KB Execution killed with signal 6
20 Runtime error 2 ms 468 KB Execution killed with signal 6
21 Runtime error 3 ms 424 KB Execution killed with signal 6
22 Runtime error 1 ms 468 KB Execution killed with signal 6
23 Runtime error 1 ms 468 KB Execution killed with signal 6
24 Runtime error 2 ms 468 KB Execution killed with signal 6
25 Runtime error 1 ms 468 KB Execution killed with signal 6
26 Runtime error 1 ms 468 KB Execution killed with signal 6
27 Runtime error 2 ms 468 KB Execution killed with signal 6
28 Runtime error 22 ms 468 KB Execution killed with signal 6
29 Runtime error 1 ms 468 KB Execution killed with signal 6
30 Runtime error 1 ms 468 KB Execution killed with signal 6
31 Runtime error 2 ms 468 KB Execution killed with signal 6
32 Runtime error 2 ms 468 KB Execution killed with signal 6
33 Runtime error 2 ms 468 KB Execution killed with signal 6
34 Runtime error 3 ms 468 KB Execution killed with signal 6
35 Runtime error 2 ms 468 KB Execution killed with signal 6
36 Runtime error 2 ms 468 KB Execution killed with signal 6
37 Runtime error 3 ms 340 KB Execution killed with signal 6
38 Runtime error 1 ms 468 KB Execution killed with signal 6
39 Runtime error 2 ms 468 KB Execution killed with signal 6
40 Runtime error 3 ms 340 KB Execution killed with signal 6
41 Runtime error 2 ms 468 KB Execution killed with signal 6
42 Runtime error 2 ms 468 KB Execution killed with signal 6
43 Runtime error 3 ms 468 KB Execution killed with signal 6
44 Runtime error 19 ms 428 KB Execution killed with signal 6
45 Runtime error 1 ms 468 KB Execution killed with signal 6