제출 #1287216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287216		ecen30	3개의 봉우리 (IOI25_triples)	C++20	35 / 100	2100 ms	164160 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;
}

// -------------------------------------------------------------
// Part I — count mythical triples
// -------------------------------------------------------------
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;
}

// -------------------------------------------------------------
// Part II — dummy construct_range (so linking succeeds)
// -------------------------------------------------------------
vector<int> construct_range(int M, int /*K*/) {
    // Minimal valid mountain range
    vector<int> H(max(3, M), 1);
    for (int i = 0; i < (int)H.size(); ++i)
        H[i] = (i % (H.size() - 1)) + 1; // any valid pattern
    return H;
}

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