Submission #1286352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286352		sampaio_kk	Triple Peaks (IOI25_triples)	C++20	18 / 100	2095 ms	23588 KiB

triples

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

// --- PARTE I: Contagem de Triplas Míticas (Solução O(N^2)) ---

/**
 * Procedimento exigido para a Parte I: Contar o número de triplas míticas.
 * Complexidade: O(N^2). Passa nas Subtasks 1 e 3.
 *
 * @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 >= 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.
            for (int d3 = 1; j + d3 < N; ++d3) {
                int k = j + d3;
                int hk = H[k];

                int d2 = d1 + d3; // d2 = k - i

                // --- 3 Casos de Correspondência (d2 deve ser o maior valor de altura) ---
                
                // Caso 1: H[i] = d2
                // 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
                // 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
                // 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 (Placeholder Simples) ---

/**
 * Procedimento exigido para a Parte II: Construir um array de picos.
 * Esta é uma implementação placeholder para fins de compilação.
 * Para obter pontuações altas na Parte II, é necessária uma construção
 * que gere O(N^2) triplas míticas.
 * * @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.
 */
std::vector<int> construct_range(int M, int K) {
    if (M < 3) {
        return {};
    }

    int N = M; // Usamos o tamanho máximo M

    std::vector<int> H(N); 
    
    // A construção mais simples e válida: H[i] = 1.
    // Garante N-2 triplas míticas, mas não o suficiente para os K grandes.
    for (int i = 0; i < N; ++i) {
        H[i] = 1;
    }
    
    // Garantir que a altura máxima não exceda N-1, mesmo que 1 seja seguro.
    if (H[0] >= N) H[0] = N - 1;


    return H;
}

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

• 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 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5