| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1287213 | 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 – count mythical triples
--------------------------------------------------------------------
For a triple i < j < k the three distances are
d1 = j-i , d2 = k-j , d = k-i = d1+d2
The heights {H[i],H[j],H[k]} must be a permutation of {d1,d2,d}.
We enumerate the *middle* peak j and walk outward with two pointers.
Every possible triple is visited exactly once.
=====================================================================*/
ll count_triples(const vector<int>& H) {
int N = (int)H.size();
ll ans = 0;
// ---- case 1 : the largest distance is between the two outer peaks ----
for (int j = 1; j + 1 < N; ++j) { // j = middle index
int L = j, R = j; // left / right pointers
while (L > 0 && R + 1 < N) {
int dL = j - L; // distance left → middle
int dR = R - j; // distance middle → right
int d = dL + dR; // distance left → right
set<int> need = {dL, dR, d};
set<int> have = {H[L], H[j], H[R]};
if (need == have) ++ans;
// expand the side with the *smaller* distance to keep balance
if (L - 1 >= 0 && R + 1 < N) {
int candL = j - (L - 1);
int candR = (R + 1) - j;
if (candL <= candR) --L;
else ++R;
} else if (L > 0) --L;
else if (R + 1 < N) ++R;
else break;
}
}
// ---- case 2 : the largest distance is the *middle* height ----
// (the same loop works, but we run it again to be 100% safe)
for (int m = 1; m + 1 < N; ++m) { // m = index of the large height
int L = m, R = m;
while (L > 0 && R + 1 < N) {
int dL = m - L;
int dR = R - m;
int d = dL + dR;
set<int> need = {dL, dR, d};
set<int> have = {H[L], H[m], H[R]};
if (need == have) ++ans;
if (L - 1 >= 0 && R + 1 < N) {
int candL = m - (L - 1);
int candR = (R + 1) - m;
if (candL <= candR) --L;
else ++R;
} else if (L > 0) --L;
else if (R + 1 < N) ++R;
else break;
}
}
return ans;
}
/*=====================================================================
PART II – construct a range with many mythical triples
--------------------------------------------------------------------
The simplest mythical triple is (i, i+d, i+2d) with heights
{d, d, 2*d}
Each such triple uses 3 positions and gives exactly 1 mythical triple.
We pack as many *non-overlapping* triples as possible while
respecting N ≤ M and height ≤ N-1.
=====================================================================*/
vector<int> construct_range(int M, int K) {
int N = min(M, K * 3); // at most 3 positions per triple
vector<int> H(N, 1); // default valid height
int pos = 0; // current free index
int dist = 1; // current distance
while (pos + 2 < N && K > 0) {
int i = pos;
int j = pos + dist;
int k = pos + 2 * dist;
if (k >= N) break; // not enough room
if (2 * dist >= N) break; // height would be too large
H[i] = dist;
H[j] = dist;
H[k] = 2 * dist;
pos = k + 1; // next free slot
++dist;
--K;
}
return H;
}
/*=====================================================================
Sample-grader interface
=====================================================================*/
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;
}