| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1284469 | kawhiet | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "triples.h"
using namespace std;
void manual(vector<int> &a) {
if (a[0] > a[1]) swap(a[0], a[1]);
if (a[1] > a[2]) swap(a[1], a[2]);
if (a[0] > a[1]) swap(a[0], a[1]);
}
long long count_triples(vector<int> h) {
int n = h.size();
auto f = [&](int i, int j, int k) {
vector<int> x = {abs(i - j), abs(i - k), abs(j - k)};
vector<int> y = {h[i], h[j], h[k]};
manual(x); manual(y);
return x == y;
};
long long res = 0;
for (int i = 0; i < n; i++) {
if (i - h[i] >= 0) {
int j = i - h[i];
int k = j + h[j];
int prv = -1;
if (k < i) {
if (f(i, j, k)) {
res++;
prv = k;
}
}
k = i - h[j];
if (k != prv && k > j) {
res += f(i, j, k);
}
}
if (i + h[i] < n) {
int j = i + h[i];
int k = j - h[j];
int prv = -1;
if (k > i) {
if (f(i, j, k)) {
res++;
prv = k;
}
}
k = i + h[j];
if (k != prv && k < j) {
res += f(i, j, k);
}
}
for (int j = max(0, i - h[i] + 1); j + h[i] <= min(n - 1, i + h[i] - 1); j++) {
int k = j + h[i];
if (j != i && k != i && h[j] + h[k] == h[i]) {
res += f(i, j, k);
}
}
}
return res;
}
// vector<int> res = {1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 2, 1, 4, 3, 2, 3, 1, 1, 2, 1};
vector<int> res = {25, 2, 1, 1, 3, 2, 3, 4, 1, 2, 1, 3, 5, 6, 5, 4, 9, 10, 7, 8, 13, 14, 3, 4, 17, 18, 1, 16, 21, 22, 19, 12, 25, 26, 9, 8, 29, 12, 11, 20, 33, 32, 31, 17, 37, 36, 3, 38, 41, 8, 31, 8, 45, 28, 27, 30, 49, 48, 47, 50, 53, 52, 19, 54, 57, 16, 47, 18, 61, 44, 43, 46, 65, 24, 55, 26, 69, 52, 35, 36, 73, 32, 63, 2, 77, 60, 59, 62, 81, 40, 71, 18, 85, 68, 51, 70, 53, 16, 79, 14};
vector<int> construct_range(int M, int K) {
vector<int> ret;
while (ret.size() < M) {
for (auto x : res) {
ret.push_back(x);
}
}
return ret;
}
int main() {
cout << count_triples(construct_range(500, 0)) << '\n';
}