Submission #1288733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288733		ecen30	Triple Peaks (IOI25_triples)	C++20	Compilation error	0 ms	0 KiB

triples

//testing Ai Code
#include "triplepeaks.h"
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

// Part I: Count mythical triples
long long count_triples(vector<int> H) {
    int N = H.size();
    long long count = 0;
    
    // For each middle peak j
    for (int j = 1; j < N - 1; j++) {
        // Count pairs (i, k) where i < j < k
        // Heights are (H[i], H[j], H[k])
        // Distances are (j-i, k-j, k-i)
        
        // Use a map to count occurrences of each height on the left
        map<int, int> left_count;
        for (int i = 0; i < j; i++) {
            left_count[H[i]]++;
        }
        
        // For each k > j
        for (int k = j + 1; k < N; k++) {
            int d1 = k - j;  // distance from j to k
            
            // For a mythical triple, we need heights to match distances
            // Distances are: (j-i, k-j, k-i) = (j-i, d1, j-i+d1)
            
            // Case 1: H[j] = j-i, so j-i = H[j], thus i = j - H[j]
            // Then we need {H[i], H[k]} = {d1, j-i+d1} = {d1, H[j]+d1}
            if (j - H[j] >= 0) {
                int i = j - H[j];
                if (i < j) {
                    // Check if {H[i], H[k]} matches {d1, H[j] + d1}
                    if ((H[i] == d1 && H[k] == H[j] + d1) ||
                        (H[i] == H[j] + d1 && H[k] == d1)) {
                        count++;
                    }
                }
            }
            
            // Case 2: H[j] = d1 (distance j to k)
            // Then we need {H[i], H[k]} to match {j-i, k-i}
            // If H[k] = j-i, then j-i = H[k], so i = j - H[k]
            if (j - H[k] >= 0 && j - H[k] < j) {
                int i = j - H[k];
                int d2 = j - i;  // = H[k]
                int d3 = k - i;  // = d2 + d1
                if (H[j] == d1 && H[i] == d3) {
                    count++;
                }
            }
            
            // Case 3: H[j] = k-i
            // Then k-i = H[j], distances are (j-i, d1, H[j])
            // We need {H[i], H[k]} = {j-i, d1}
            // If H[i] = j-i, then i such that j-i = H[i]
            // If H[k] = j-i, then we need to check
            int d3_target = H[j];  // k - i should equal H[j]
            int i_candidate = k - d3_target;
            if (i_candidate >= 0 && i_candidate < j) {
                int d2 = j - i_candidate;
                if ((H[i_candidate] == d2 && H[k] == d1) ||
                    (H[i_candidate] == d1 && H[k] == d2)) {
                    count++;
                }
            }
        }
    }
    
    // The above counts each triple multiple times, need to fix
    // Actually, let me rewrite with correct logic
    
    count = 0;
    for (int i = 0; i < N - 2; i++) {
        for (int j = i + 1; j < N - 1; j++) {
            for (int k = j + 1; k < N; k++) {
                int d1 = j - i;
                int d2 = k - i;
                int d3 = k - j;
                
                vector<int> heights = {H[i], H[j], H[k]};
                vector<int> distances = {d1, d2, d3};
                
                sort(heights.begin(), heights.end());
                sort(distances.begin(), distances.end());
                
                if (heights == distances) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

// Part II: Construct mountain range with many mythical triples
vector<int> construct_range(int M, int K) {
    // Strategy: Create patterns that generate many mythical triples
    
    // Pattern 1: Repeating sequence that creates many triples
    // A simple pattern: use heights that are small and repeat
    // Heights like [1, 2, 1, 2, 1, 2, ...] can create triples
    
    // Better pattern: Use arithmetic progressions
    // For large M, we want to maximize triples
    
    vector<int> H;
    
    if (M <= 100) {
        // Small case: use pattern [1, 2, 3, 1, 2, 3, ...]
        int pattern_len = min(M, 10);
        for (int i = 0; i < M; i++) {
            H.push_back((i % pattern_len) + 1);
        }
    } else {
        // Large case: use a pattern that maximizes triples
        // Pattern: mostly 1s and 2s which create many small distance triples
        int n = min(M, 200000);
        for (int i = 0; i < n; i++) {
            if (i % 3 == 0) H.push_back(1);
            else if (i % 3 == 1) H.push_back(2);
            else H.push_back(1);
        }
    }
    
    // Ensure heights are valid (between 1 and N-1)
    int N = H.size();
    for (int i = 0; i < N; i++) {
        if (H[i] >= N) H[i] = N - 1;
        if (H[i] < 1) H[i] = 1;
    }
    
    return H;
}

Compilation message (stderr)

triples.cpp:2:10: fatal error: triplepeaks.h: No such file or directory
    2 | #include "triplepeaks.h"
      |          ^~~~~~~~~~~~~~~
compilation terminated.