| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1286349 | sampaio_kk | 3개의 봉우리 (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
#include <iostream>
/**
* Função principal para contar triplas míticas.
* Complexidade: O(N^2)
* Passa nas subtasks com N pequeno (N <= 2000).
* * @param H Array de alturas dos picos.
* @return O número total de triplas míticas.
*/
long long count_triples(std::vector<int> H) {
int N = H.size();
long long count = 0;
// Iteração sobre o índice central 'j'
// j varia de 1 (precisa de i < j) até N-2 (precisa de k > j)
for (int j = 1; j < N - 1; ++j) {
// Iteração sobre a distância esquerda 'd1' (d1 = j - i)
// d1 varia de 1 até j.
for (int d1 = 1; d1 <= j; ++d1) {
int i = j - d1;
int hi = H[i];
int hj = H[j];
// A distância d3 (k - j) deve ser pelo menos 1
// e no máximo N - 1 - j.
for (int d3 = 1; j + d3 < N; ++d3) {
int k = j + d3;
int hk = H[k];
// d2 é a distância total entre i e k.
int d2 = d1 + d3;
// --- Verificação da Condição de Tripla Mítica ---
// O conjunto de alturas {hi, hj, hk} deve ser uma permutação
// do conjunto de distâncias {d1, d2, d3}.
// O truque é usar a propriedade de que d2 é a SOMA dos outros dois.
// Na condição mítica, a MAIOR altura deve ser igual a d2, ou:
// SOMA DAS ALTURAS - MAIOR ALTURA = MENOR ALTURA + MEIO ALTURA = d1 + d3 = d2
// Opção 1: d2 corresponde a H[i]
// Condição: H[i] == d2 E {H[j], H[k]} == {d1, d3}
if (hi == d2) {
if ((hj == d1 && hk == d3) || (hj == d3 && hk == d1)) {
count++;
continue; // Tripla encontrada, ir para a próxima d3
}
}
// Opção 2: d2 corresponde a H[j]
// Condição: H[j] == d2 E {H[i], H[k]} == {d1, d3}
if (hj == d2) {
if ((hi == d1 && hk == d3) || (hi == d3 && hk == d1)) {
count++;
continue; // Tripla encontrada, ir para a próxima d3
}
}
// Opção 3: d2 corresponde a H[k]
// Condição: H[k] == d2 E {H[i], H[j]} == {d1, d3}
if (hk == d2) {
if ((hi == d1 && hj == d3) || (hi == d3 && hj == d1)) {
count++;
continue; // Tripla encontrada, ir para a próxima d3
}
}
}
}
}
return count;
}
/* // Exemplo de uso (Para teste local):
int main() {
// Exemplo do enunciado: [4, 1, 4, 3, 2, 6, 1]
// Resultado esperado: 3
std::vector<int> example1 = {4, 1, 4, 3, 2, 6, 1};
std::cout << "Resultado (Exemplo 1): " << count_triples(example1) << std::endl;
// Triplas: (1,3,4) -> (1,3,2) vs (2,3,1); (2,3,6) -> (4,3,1) vs (1,4,3); (3,4,6) -> (3,2,1) vs (1,3,2)
// Outro exemplo (Não mítico): (0,2,4) de [4, 1, 4, 3, 2, 6, 1]
// Alturas: (4, 4, 2)
// Distâncias: d1=2, d3=2, d2=4. Conjunto: {2, 2, 4}
// As alturas (4, 4, 2) não são uma permutação de {2, 2, 4} (pois as alturas têm dois 4s)
// Exemplo Simples (1, 2, 3)
// i=0, j=1, k=2. Distâncias: d1=1, d3=1, d2=2. Conjunto: {1, 1, 2}
// H = [1, 1, 2] -> Mítica (hi=1, hj=1, hk=2)
// H = [1, 2, 1] -> Mítica
// H = [2, 1, 1] -> Mítica
std::vector<int> example2 = {1, 1, 2};
std::cout << "Resultado (Exemplo 2): " << count_triples(example2) << std::endl;
return 0;
}
*/