Submission #1256663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256663		jamesbamber	Triple Peaks (IOI25_triples)	C++20	43.84 / 100	2095 ms	1864 KiB

triples

#include "triples.h"
#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;

long long count_triples(std::vector<int> H) {
    int N = H.size();
    ll ct = 0;

    auto check_triple = [&](int i, int j, int k) -> void {
        
        if(i < 0 or i >= N or j < 0 or j >= N or k < 0 or k >= N or i == j or i == k or j == k) return;
        if(H[i] <= H[j] or H[i] <= H[k]) return; //check that i is the tallest

        // cerr << i << " " << j << " " << k << endl;

        vector<int> ids = {H[i], H[j], H[k]};
        vector<int> diffs = {abs(i-j), abs(i-k), abs(j-k)};

        sort(ids.begin(), ids.end());
        sort(diffs.begin(), diffs.end());

        if(ids == diffs) ct++;
    };

    bool sorted = is_sorted(H.begin(), H.end());

    for(int i=0; i<N; i++) {
        // max non al centro
        if(i - H[i] >= 0) {
            int j = i - H[i];
            check_triple(i, j, j + H[j]);
            if(i - H[j] != j + H[j]) check_triple(i, j, i - H[j]);
        }

        if(i + H[i] < N) {
            int j = i + H[i];
            check_triple(i, j, j - H[j]);
            if(i + H[j] != j - H[j]) check_triple(i, j, i + H[j]);
        }

        // max al centro
        if(sorted) continue;

        for(int j=max(0, i-H[i]+1); j<i and j+H[i]<N; j++){
            check_triple(i, j, j+H[i]);
        }
    }

    return ct;
}

std::vector<int> construct_range(int M, int K) {
    vector<int> good_seq = {2, 1, 1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 2, 1, 4, 3, 2, 3, 1, 1, 2, 3, 2, 1, 1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 2, 1, 4, 3, 2, 3, 1, 1, 2};

    vector<int> ans(M);
    for(int i=0; i<M; i++) ans[i] = good_seq[i%good_seq.size()];
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 5 / 5
• Subtask 8: 2.085 / 5
• Subtask 9: 0.8369 / 5
• Subtask 10: 0.3588 / 5
• Subtask 11: 0.4186 / 5
• Subtask 12: 0.1395 / 5