| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1287044 | ecen30 | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
//Testing AI COde
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/* --------------------------------------------------------------
PART I – counting mythical triples
-------------------------------------------------------------- */
ll count_triples(const vector<int>& H) {
int n = (int)H.size();
if (n < 3) return 0;
ll answer = 0;
// --------------------------------------------------------------
// 1) For every possible middle peak j we try all possible
// distances a = j-i, b = k-j (a,b ≥ 1)
// The three distances are a, b, a+b.
// The three heights must be {a, b, a+b} (any order).
// --------------------------------------------------------------
for (int j = 1; j + 1 < n; ++j) { // j is the middle index
int hj = H[j];
// ---- left side (i = j - a) --------------------------------
vector<int> cnt_left(n + 1, 0); // cnt_left[d] = #peaks at distance d left of j
for (int a = 1; j - a >= 0; ++a) {
int i = j - a;
int hi = H[i];
if (hi > n) continue; // impossible because 1 ≤ H[i] ≤ n-1
++cnt_left[hi];
}
// ---- right side (k = j + b) -------------------------------
for (int b = 1; j + b < n; ++b) {
int k = j + b;
int hk = H[k];
// the three distances: a, b, a+b
// the three heights: H[i], hj, hk (i = j-a)
// We need {hi, hj, hk} == {a, b, a+b}
// Instead of enumerating a we check the three possible
// assignments of hk to the missing distance.
int need1 = hk; // suppose hk = a
int need2 = hj - hk; // then b = hj - a
int need3 = b - need1; // a+b - a = b (always true)
if (need1 >= 1 && need2 >= 1 && need1 + need2 == hj) {
// distances: a=need1, b=need2, a+b=hj
// left distance = a = need1
answer += cnt_left[need1];
continue; // one possibility is enough for this (j,b)
}
// second case: hk = b
int needA = hj - hk; // a = hj - b
if (needA >= 1 && hk + needA == hj) {
answer += cnt_left[needA];
continue;
}
// third case: hk = a+b (i.e. hk == hj)
if (hk == hj) {
// a + b = hj, a = ?, b = ?
// we need a height a on the left side
// for every possible a (1 … hj-1) with b = hj-a
// count peaks i with H[i] == a
for (int a = 1; a < hj; ++a) {
int bb = hj - a;
if (bb >= 1 && bb <= n) {
answer += cnt_left[a];
}
}
}
}
}
// --------------------------------------------------------------
// 2) The above loop counts each triple exactly once
// (the middle peak is the one whose height equals the largest
// distance a+b). This works for all configurations.
// --------------------------------------------------------------
return answer;
}
/* --------------------------------------------------------------
PART II – constructing a range with many triples
-------------------------------------------------------------- */
vector<int> construct_range(int M, int K) {
// ------------------------------------------------------------------
// Idea: use an arithmetic progression with a very small common
// difference (here 1). The array 1,2,3,…,N-1,1,2,…,N-1,…
// creates huge numbers of triples because many index
// differences equal the heights that appear many times.
// ------------------------------------------------------------------
int N = M; // use the whole allowed size
vector<int> H(N);
for (int i = 0; i < N; ++i) {
H[i] = (i % (N - 1)) + 1; // values 1 … N-1 repeatedly
}
return H;
}
/* --------------------------------------------------------------
MAIN – dispatcher for the sample grader
-------------------------------------------------------------- */
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int part;
if (!(cin >> part)) return 0;
if (part == 1) { // ---------- PART I ----------
int N;
cin >> N;
vector<int> H(N);
for (int i = 0; i < N; ++i) cin >> H[i];
cout << count_triples(H) << '\n';
} else if (part == 2) { // ---------- PART II ----------
int M, K;
cin >> M >> K;
vector<int> H = construct_range(M, K);
cout << H.size();
for (int h : H) cout << ' ' << h;
cout << '\n';
}
return 0;
}