Submission #1307049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307049		MunkhErdene	Triple Peaks (IOI25_triples)	C++17	16.29 / 100	54 ms	37128 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static inline uint64_t pack_triple(int i, int j, int k) {
    return (uint64_t(i) << 42) | (uint64_t(j) << 21) | uint64_t(k);
}

long long count_triples(std::vector<int> H) {
    int n = (int)H.size();
    vector<ll> a(H.begin(), H.end());
    vector<array<int,3>> candidates;
    candidates.reserve(n * 6);

    for (int i = 0; i < n; ++i) {
        {
            ll j = (ll)i + a[i];
            if (0 <= j && j < n) {
                ll k = j + a[j];
                if (0 <= k && k < n) candidates.push_back({i, int(j), int(k)});
            }
        }
        {
            ll j = (ll)i + a[i];
            if (0 <= j && j < n) {
                ll k = (ll)i + a[j];
                if (0 <= k && k < n) candidates.push_back({i, int(j), int(k)});
            }
        }
        {
            ll k = (ll)i + a[i];
            if (0 <= k && k < n) {
                ll j = k - a[k];
                if (0 <= j && j < n) candidates.push_back({i, int(j), int(k)});
            }
        }
    }

    for (int j = 0; j < n; ++j) {
        {
            ll i = (ll)j - a[j];
            if (0 <= i && i < n) {
                ll k = j + a[i];
                if (0 <= k && k < n) candidates.push_back({int(i), j, int(k)});
            }
        }
        {
            ll k = (ll)j + a[j];
            if (0 <= k && k < n) {
                // i = j - H[k]
                ll i = (ll)j - a[k];
                if (0 <= i && i < n) candidates.push_back({int(i), j, int(k)});
            }
        }
    }

    for (int k = 0; k < n; ++k) {
        // j = k - H[k]; i = k - H[j]
        ll j = (ll)k - a[k];
        if (0 <= j && j < n) {
            ll i = (ll)k - a[j];
            if (0 <= i && i < n) candidates.push_back({int(i), int(j), k});
        }
    }

    unordered_set<uint64_t> seen;
    seen.reserve(candidates.size() * 2 + 16);
    ll ans = 0;

    for (auto &t : candidates) {
        int i = t[0], j = t[1], k = t[2];
        if (!(0 <= i && i < j && j < k && k < n)) continue; 

        uint64_t key = pack_triple(i,j,k);
        if (seen.find(key) != seen.end()) continue;

        array<int,3> Hvals = { H[i], H[j], H[k] };
        sort(Hvals.begin(), Hvals.end());
        int d1 = j - i;
        int d2 = k - j;
        int d3 = k - i;
        array<int,3> Dvals = { d1, d2, d3 };
        sort(Dvals.begin(), Dvals.end());
        if (Hvals == Dvals) {
            seen.insert(key);
            ++ans;
        }
    }

    return ans;
}

std::vector<int> construct_range(int M, int K) {
    vector<int> res(M);
    iota(res.begin(), res.end(), 0);
    res[0] = 1;
    return res;
}

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