#include "triples.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N_MAX = 2e5 + 11;
int N;
int H[N_MAX];
bool in(int x) {
return 0 <= x && x < N;
}
bool check(int a, int b, int c) {
if (!in(a) || !in(b) || !in(c) || a >= b || b >= c) return false;
return multiset<int>{H[a], H[b], H[c]} == multiset<int>{abs(a - b), abs(a - c), abs(b - c)};
}
int ans = 0;
set<tuple<int, int, int>> S;
bool check_set(int a, int b, int c) {
bool ok = check(a, b, c);
if (!ok) return false;
if (S.count({a, b, c})) return false;
S.insert({a, b, c}); ans++; return true;
}
int count_triples(vector<int32_t> H) {
N = H.size();
for (int i = 0; i < N; i++) ::H[i] = H[i];
for (int i = 0; i < N; i++) {
int a = i;
{
int b = a - H[a];
if (in(b)) {
int c = b + H[b];
check_set(b, a, c);
}
if (in(b)) {
int c = a + H[b];
check_set(b, a, c);
}
}
{
int b = a + H[a];
if (in(b)) {
int c = b - H[b];
check_set(c, a, b);
}
if (in(b)) {
int c = a - H[b];
check_set(c, a, b);
}
}
}
for (int a = 0; a < N; a++) {
for (int c = a + 2; c < a + 30; c++) {
check_set(a, a + H[a], c);
check_set(a, a + H[c], c);
}
}
return ans;
}
vector<int32_t> construct_range(int32_t M, int32_t _K) {
const int K = sqrt(M);
M = M / K * K - 1;
vector<int32_t> ans(M);
int B = M / K;
for (int i = 0; i < B; i++) {
for (int j = 0; j < K; j++) {
ans[i * K + j] = K * (B - 1 - i) + 1 + j;
}
}
for (int j = 0; j < K - 1; j++) {
ans[B * K + j] = K - 1 - j;
}
// cout << "ANS = " << count_triples(ans) << endl;
return ans;
}
# | 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... |