Submission #1307047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307047		MunkhErdene	Triple Peaks (IOI25_triples)	C++17	16.29 / 100	62 ms	37020 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define _ << ' ' <<
using ll = long long;
long long count_triples(std::vector<int> H) {
    int n = (int)H.size();
    vector<array<int,3>> cand;
    cand.reserve(n * 6);

    for (int i = 0; i < n; ++i) {
        {
            int j = i + H[i];
            if (j < n) {
                long long kll = (long long)j + H[j];
                if (kll < n) {
                    int k = (int)kll;
                    if (i < j && j < k)
                        cand.push_back({i,j,k});
                }
            }
        }

        {
            int j = i + H[i];
            if (j < n) {
                long long kll = (long long)i + H[j];
                if (kll < n) {
                    int k = (int)kll;
                    if (i < j && j < k)
                        cand.push_back({i,j,k});
                }
            }
        }

        {
            long long kll = (long long)i + H[i];
            if (kll < n) {
                int k = (int)kll;
                long long jll = (long long)k - H[k];
                if (0 <= jll && jll < n) {
                    int j = (int)jll;
                    if (i < j && j < k)
                        cand.push_back({i,j,k});
                }
            }
        }
    }

    for (int j = 0; j < n; ++j) {
        {
            int i = j - H[j];
            if (0 <= i) {
                long long kll = (long long)j + H[i];
                if (kll < n) {
                    int k = (int)kll;
                    if (i < j && j < k)
                        cand.push_back({i,j,k});
                }
            }
        }

        {
            long long kll = (long long)j + H[j];
            if (kll < n) {
                int k = (int)kll;
                long long ill = (long long)j - H[k];
                if (0 <= ill && ill < n) {
                    int i = (int)ill;
                    if (i < j && j < k)
                        cand.push_back({i,j,k});
                }
            }
        }
    }

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

    for (auto &t : cand) sort(t.begin(), t.end());

    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());

    long long ans = 0;
    for (auto &t : cand) {
        int i = t[0], j = t[1], k = t[2];
        array<int,3> d = { j - i, k - j, k - i };
        array<int,3> h = { H[i], H[j], H[k] };
        sort(d.begin(), d.end());
        sort(h.begin(), h.end());
        if (d == h) ++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