#include <bits/stdc++.h>
bool check(int a, int b, int c, int x, int y, int z) {
std::array<int, 3> p = {a, b, c};
std::array<int, 3> q = {x, y, z};
std::sort(p.begin(), p.end());
std::sort(q.begin(), q.end());
return p == q;
}
long long count_triples(std::vector<int> H) {
const int n = H.size();
long long ans = 0;
// case 1
for (int i = 0; i < n; ++i) {
int j = H[i] + i;
if (0 <= j and j < n) {
for (int k = j + 1; k < n; ++k) {
ans += check(j - i, k - j, k - i, H[i], H[j], H[k]);
}
}
}
// not case 1 but case 2
for (int j = 0; j < n; ++j) {
int i = j - H[j];
if (0 <= i and i < n and j != H[i] + i) {
for (int k = j + 1; k < n; ++k) {
ans += check(j - i, k - j, k - i, H[i], H[j], H[k]);
}
}
}
// not case 1 or case 2 but case 3.1
// so a[i] + i != j and i != j - a[j]
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int k = H[i] + i;
if (k != H[j] + j or H[i] + i == j or i == j - H[j]) {
continue;
}
if (0 <= k and k < n) {
ans += check(j - i, k - j, k - i, H[i], H[j], H[k]);
}
}
}
// not case 1 or case 2 or case 3.1 but case 3.2
// so NOT a[i] + i == j or i == j - a[j] or k == a[i] + i == a[j] + j
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int k = H[i] + j;
if (k != H[j] + i or H[i] + i == j or i == j - H[i] or
(k == H[i] + i and k == H[j] + j)) {
continue;
}
if (0 <= k and k < n) {
ans += check(j - i, k - j, k - i, H[i], H[j], H[k]);
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) { return {1, 1, 1}; }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |