| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1287050 | ecen30 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
//AI code testing
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*===================================================================
PART I – count the number of mythical triples
Time: 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 in the triple
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];
continue;
}
// Case 2: hk == b → a = hj - b
if (hk >= 1 && hj - hk >= 1 && (hj - hk) + hk == hj) {
ans += left_cnt[hj - hk];
continue;
}
// Case 3: hk == a+b (= hj)
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 pattern 1,2,...,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;
}