| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1287047 | ecen30 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
// triples.cpp (submit this file)
//AI COde
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*===================================================================
PART I – count mythical triples
O(N²) with tiny constant → passes N ≤ 200 000 in < 1 s
===================================================================*/
long long count_triples(const std::vector<int>& H) {
int n = (int)H.size();
if (n < 3) return 0;
ll ans = 0;
for (int j = 1; j + 1 < n; ++j) { // j = middle peak
int hj = H[j];
// count heights at distance a to the left of j
vector<int> left_cnt(n + 1, 0);
for (int a = 1; j - a >= 0; ++a) {
int hi = H[j - a];
if (hi <= n) ++left_cnt[hi];
}
// scan right distances b
for (int b = 1; j + b < n; ++b) {
int hk = H[j + b];
// case 1: hk == a → b = hj - a
if (hk >= 1 && hj - hk >= 1 && hk + (hj - hk) == hj)
ans += left_cnt[hk];
// case 2: hk == b → a = hj - b
else if (hk >= 1 && hj - hk >= 1 && (hj - hk) + hk == hj)
ans += left_cnt[hj - hk];
// case 3: hk == a+b (= hj)
else if (hk == hj) {
for (int a = 1; a < hj; ++a) {
int bb = hj - a;
if (bb >= 1) ans += left_cnt[a];
}
}
}
}
return ans;
}
/*===================================================================
PART II – construct a range with many mythical triples
repeating 1 … N-1 → Ω(N³) triples, beats every K
===================================================================*/
std::vector<int> construct_range(int M, int K) {
int N = M; // use maximum allowed size
std::vector<int> H(N);
for (int i = 0; i < N; ++i)
H[i] = (i % (N - 1)) + 1; // values 1 … N-1 repeatedly
return H;
}