| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1287215 | ecen30 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
//testing AI code
#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
// -------------------------------------------------------------
// helper: check if triple (i,j,k) is mythical
// -------------------------------------------------------------
static inline bool is_mythical(int i, int j, int k, const vector<int>& H) {
array<int,3> h = {H[i], H[j], H[k]};
array<int,3> d = {j - i, k - j, k - i};
sort(h.begin(), h.end());
sort(d.begin(), d.end());
return h == d;
}
// -------------------------------------------------------------
// main counting function for Part I
// -------------------------------------------------------------
long long count_triples(vector<int> H) {
const int n = (int)H.size();
long long total = 0;
set<array<int,3>> used;
// ---- Phase 1: explore close triples via (i, i ± H[i]) ----
auto try_pair = [&](int p, int q) {
if (p < 0 || q < 0 || p >= n || q >= n || p == q) return;
for (int idx : {p, q}) {
for (int step : {H[p], H[q]}) {
for (int r : {idx - step, idx + step}) {
if (r < 0 || r >= n || r == p || r == q) continue;
array<int,3> t = {p, q, r};
sort(t.begin(), t.end());
if (used.insert(t).second && is_mythical(t[0], t[1], t[2], H))
total++;
}
}
}
};
for (int i = 0; i < n; ++i) {
for (int j : {i - H[i], i + H[i]})
if (0 <= j && j < n) try_pair(i, j);
}
// ---- Phase 2: diagonal matching to capture remaining triples ----
unordered_map<int, vector<int>> diag_sum, diag_diff;
diag_sum.reserve(n * 2);
diag_diff.reserve(n * 2);
for (int i = 0; i < n; ++i) {
diag_sum[i + H[i]].push_back(i);
diag_diff[i - H[i]].push_back(i);
}
auto check_and_add = [&](int i, int j, int k) {
if (!(0 <= i && i < j && j < k && k < n)) return;
array<int,3> t = {i, j, k};
if (used.insert(t).second && is_mythical(i, j, k, H))
total++;
};
for (int j = 0; j < n; ++j) {
auto& L = diag_sum[j + H[j]];
auto& R = diag_diff[j - H[j]];
if (L.size() < R.size()) {
for (int k : L) {
int i = k - H[j];
check_and_add(i, j, k);
}
} else {
for (int i : R) {
if (i < j) {
int k = i + H[j];
check_and_add(i, j, k);
}
}
}
}
return total;
}