Submission #1287215

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

triples

//testing AI code
#include "triples.h"
#include <bits/stdc++.h>
using namespace std;

// -------------------------------------------------------------
// helper: check if triple (i,j,k) is mythical
// -------------------------------------------------------------
static inline bool is_mythical(int i, int j, int k, const vector<int>& H) {
    array<int,3> h = {H[i], H[j], H[k]};
    array<int,3> d = {j - i, k - j, k - i};
    sort(h.begin(), h.end());
    sort(d.begin(), d.end());
    return h == d;
}

// -------------------------------------------------------------
// main counting function for Part I
// -------------------------------------------------------------
long long count_triples(vector<int> H) {
    const int n = (int)H.size();
    long long total = 0;
    set<array<int,3>> used;

    // ---- Phase 1: explore close triples via (i, i ± H[i]) ----
    auto try_pair = [&](int p, int q) {
        if (p < 0 || q < 0 || p >= n || q >= n || p == q) return;
        for (int idx : {p, q}) {
            for (int step : {H[p], H[q]}) {
                for (int r : {idx - step, idx + step}) {
                    if (r < 0 || r >= n || r == p || r == q) continue;
                    array<int,3> t = {p, q, r};
                    sort(t.begin(), t.end());
                    if (used.insert(t).second && is_mythical(t[0], t[1], t[2], H))
                        total++;
                }
            }
        }
    };

    for (int i = 0; i < n; ++i) {
        for (int j : {i - H[i], i + H[i]})
            if (0 <= j && j < n) try_pair(i, j);
    }

    // ---- Phase 2: diagonal matching to capture remaining triples ----
    unordered_map<int, vector<int>> diag_sum, diag_diff;
    diag_sum.reserve(n * 2);
    diag_diff.reserve(n * 2);

    for (int i = 0; i < n; ++i) {
        diag_sum[i + H[i]].push_back(i);
        diag_diff[i - H[i]].push_back(i);
    }

    auto check_and_add = [&](int i, int j, int k) {
        if (!(0 <= i && i < j && j < k && k < n)) return;
        array<int,3> t = {i, j, k};
        if (used.insert(t).second && is_mythical(i, j, k, H))
            total++;
    };

    for (int j = 0; j < n; ++j) {
        auto& L = diag_sum[j + H[j]];
        auto& R = diag_diff[j - H[j]];

        if (L.size() < R.size()) {
            for (int k : L) {
                int i = k - H[j];
                check_and_add(i, j, k);
            }
        } else {
            for (int i : R) {
                if (i < j) {
                    int k = i + H[j];
                    check_and_add(i, j, k);
                }
            }
        }
    }

    return total;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccXTQDdV.o: in function `main':
grader.cpp:(.text.startup+0x197): undefined reference to `construct_range(int, int)'
collect2: error: ld returned 1 exit status