제출 #1286350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286350		sampaio_kk	Triple Peaks (IOI25_triples)	C++20	18.17 / 100	2095 ms	1952 KiB

triples

#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <numeric>

// --- PARTE I: Contagem de Triplas Míticas (O(N^2) Solution) ---

/**
 * Procedimento exigido para a Parte I: Contar o número de triplas míticas.
 * Complexidade: O(N^2)
 *
 * @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;

    // A condição é que {H[i], H[j], H[k]} seja uma permutação de {d1, d2, d3},
    // onde d1 = j-i, d3 = k-j, e d2 = d1 + d3.
    // Otimizamos iterando sobre o índice central 'j' e a distância 'd1'.

    // Iteração sobre o índice central 'j'
    for (int j = 1; j < N - 1; ++j) {

        // Iteração sobre a distância esquerda 'd1' (d1 = j - i).
        // d1 >= 1.
        for (int d1 = 1; d1 <= j; ++d1) {
            
            int i = j - d1;
            int hi = H[i];
            int hj = H[j];

            // Iteração sobre a distância direita 'd3' (d3 = k - j).
            // d3 >= 1 e k < N, então d3 <= N - 1 - j.
            for (int d3 = 1; j + d3 < N; ++d3) {
                int k = j + d3;
                int hk = H[k];

                int d2 = d1 + d3; 

                // --- 3 Casos de Correspondência (d2 é o maior valor) ---
                
                // Caso 1: H[i] = d2 (a maior altura é a primeira)
                // H[j] e H[k] devem ser {d1, d3}
                if (hi == d2) {
                    if ((hj == d1 && hk == d3) || (hj == d3 && hk == d1)) {
                        count++;
                        continue; 
                    }
                }

                // Caso 2: H[j] = d2 (a maior altura é a central)
                // H[i] e H[k] devem ser {d1, d3}
                if (hj == d2) {
                    if ((hi == d1 && hk == d3) || (hi == d3 && hk == d1)) {
                        count++;
                        continue;
                    }
                }

                // Caso 3: H[k] = d2 (a maior altura é a última)
                // H[i] e H[j] devem ser {d1, d3}
                if (hk == d2) {
                    if ((hi == d1 && hj == d3) || (hi == d3 && hj == d1)) {
                        count++;
                        continue;
                    }
                }
            }
        }
    }

    return count;
}


// --- PARTE II: Construção de Picos (Função Placeholder) ---

/**
 * Procedimento exigido para a Parte II: Construir um array de picos.
 * ESTA É UMA IMPLEMENTAÇÃO PLACEHOLDER (Para fins de compilação/teste de Part I).
 * Para obter pontuações na Parte II, é necessária uma estratégia de construção otimizada.
 *
 * @param M O número máximo de picos.
 * @param K O número desejado de triplas míticas.
 * @return Um array H de alturas, onde 3 <= H.size() <= M, e 1 <= H[i] <= H.size() - 1.
 */
std::vector<int> construct_range(int M, int K) {
    // A construção mais simples e válida. O tamanho mínimo é 3[cite: 48].
    // N = 3. Alturas devem estar entre 1 e N-1 (ou seja, 1 e 2)[cite: 48].
    // H = [1, 2, 1]. Esta configuração tem 1 tripla mítica: (0, 1, 2).
    // Distâncias: {1, 2, 1}. Alturas: {1, 2, 1}. Match.

    if (M >= 3) {
        // Retorna N=3 com H=[1, 2, 1]
        return {1, 2, 1}; 
    }
    // Caso M < 3 (não deve ocorrer, mas é uma contingência)
    return {};
}

// --- FIM DOS PROCEDIMENTOS IOI ---

/*
// Exemplo de uso para um ambiente de teste local:
int main() {
    // --- Teste da Parte I ---
    std::cout << "--- Teste da Parte I: count_triples ---" << std::endl;
    
    // Exemplo do enunciado: [4, 1, 4, 3, 2, 6, 1]
    // Resultado esperado: 3 [cite: 34, 38]
    std::vector<int> H_exemplo = {4, 1, 4, 3, 2, 6, 1};
    std::cout << "Exemplo 1 (Resultado esperado: 3): " << count_triples(H_exemplo) << std::endl; 
    
    // Exemplo Simples (N=3, i=0, j=1, k=2)
    // Distâncias: {1, 2, 1}. Alturas: {1, 2, 1}. Mítica.
    std::vector<int> H_simples = {1, 2, 1};
    std::cout << "Exemplo 2 ([1, 2, 1]): " << count_triples(H_simples) << std::endl; 
    
    // Exemplo Simples (N=4)
    // H = [1, 1, 1, 1]. Triplas: (0, 1, 2), (1, 2, 3) (Míticas? Não. {1,2,1} vs {1,1,1})
    // Triplas: (0, 1, 2) -> {1, 2, 1} vs {1, 1, 1} (Não)
    // Triplas: (0, 2, 3) -> {2, 3, 1} vs {1, 1, 1} (Não)
    // Triplas: (0, 1, 3) -> {1, 3, 2} vs {1, 1, 1} (Não)
    std::vector<int> H_quatro = {1, 1, 1, 1};
    std::cout << "Exemplo 3 ([1, 1, 1, 1] - esperado: 0): " << count_triples(H_quatro) << std::endl; 
    

    // --- Teste da Parte II (Placeholder) ---
    std::cout << "\n--- Teste da Parte II: construct_range (Placeholder) ---" << std::endl;
    
    int M_teste = 10;
    int K_teste = 100;
    std::vector<int> range = construct_range(M_teste, K_teste);
    
    std::cout << "Array Construído (N=" << range.size() << "): ";
    for (int h : range) {
        std::cout << h << " ";
    }
    std::cout << std::endl;

    return 0;
}
*/

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 0.1667 / 5
• Subtask 8: 0.0025 / 5
• Subtask 9: 0.0001 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5