| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1290818 | ecen30 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
//testing AI code
#include <vector>
#include <unordered_map>
long long count_triples(const std::vector<int>& H) {
long long result = 0;
int N = H.size();
std::unordered_map<int, std::vector<int>> positions;
// Precompute for each valid height, all positions where it appears
for (int idx = 0; idx < N; ++idx)
positions[H[idx]].push_back(idx);
// For every possible pair (i, k), try to find j in between such that
// the triple satisfies the condition
for (int i = 0; i < N; ++i) {
for (int k = i + 2; k < N; ++k) {
int d2 = k - i; // distance from i to k
int h1 = H[i], h3 = H[k];
// The only possible j must be i < j < k
// The distances between the three indices are: j-i, k-i, k-j
// so the triple of distances (d1, d2, d3) where:
// d1 = j-i
// d2 = k-i
// d3 = k-j = k-i - (j-i)
// Thus for a given (i, k), we want to pick j so that the heights H[i], H[j], H[k]
// are a permutation of (j-i, k-i, k-j)
// For all possible j between i+1 and k-1
for (int j = i + 1; j < k; ++j) {
std::vector<int> dists = {j - i, k - i, k - j};
std::vector<int> heights = {H[i], H[j], H[k]};
std::sort(dists.begin(), dists.end());
std::sort(heights.begin(), heights.end());
if (dists == heights)
result++;
}
}
}
return result;
}