Submission #1250212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250212		ezzzay	Triple Peaks (IOI25_triples)	C++20	4.95 / 100	13 ms	1860 KiB

triples

#include "triples.h"
#include <vector>
using namespace std;

// Part I: O(N) count by handling the three ways the two smallest distances
// can come from two of the heights.
long long count_triples(vector<int> H) {
    int N = H.size();
    long long ans = 0;

    // Case A: the two *smallest* distances are d(i,j) = H[i] and d(j,k) = H[j].
    //   ⇒ j = i + H[i],  k = j + H[j],  and H[k] must equal H[i] + H[j].
    for(int i = 0; i < N; i++){
        int j = i + H[i];
        if(j < N){
            int k = j + H[j];
            if(k < N && H[k] == H[i] + H[j]) {
                ans++;
            }
        }
    }

    // Case B: the two *smallest* distances are d(i,j) = H[i] and d(i,k) = H[k].
    //   ⇒ j = k - H[k],  k = i + H[i],  and H[j] + H[k] == H[i] + H[j]?  Actually:
    // we want {H[i],H[j],H[k]} = {H[i],H[k], H[i]+H[k]}, so H[j] == H[i] + H[k].
    for(int i = 0; i < N; i++){
        int k = i + H[i];
        if(k < N){
            int j = k - H[k];
            if(j > i && j < N && H[j] == H[i] + H[k]) {
                ans++;
            }
        }
    }

    // Case C: the two *smallest* distances are d(i,k) = H[k] and d(j,k) = H[j].
    //   ⇒ i = j - H[j],  k = j + H[j],  and H[i] + H[k] == H[j].
    for(int j = 0; j < N; j++){
        int i = j - H[j];
        int k = j + H[j];
        if(i >= 0 && k < N && H[i] + H[k] == H[j]) {
            ans++;
        }
    }

    return ans;
}

// Part II: pack as many [1,1,2] blocks as will fit in M:
// each block is size 3 and contributes exactly one mythical triple.
vector<int> construct_range(int M, int K) {
    int blocks = M / 3;         // maximum disjoint [1,1,2] blocks
    int want  = min(blocks, K); // if K smaller, only need K blocks

    int N = want * 3;
    if(N < 3) {
        // must output at least 3 peaks
        return vector<int>{1,1,2};
    }

    vector<int> H;
    H.reserve(N);
    for(int b = 0; b < want; b++){
        H.push_back(1);
        H.push_back(1);
        H.push_back(2);
    }
    return H;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 2.6667 / 5
• Subtask 8: 1.24 / 5
• Subtask 9: 0.4996 / 5
• Subtask 10: 0.2143 / 5
• Subtask 11: 0.25 / 5
• Subtask 12: 0.0833 / 5