Submission #1263260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263260		Sharky	Triple Peaks (IOI25_triples)	C++20	70 / 100	1604 ms	73096 KiB

triples

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

set<array<int, 3>> ez;
map<int, vector<int>> va;
int Fa[400001];
vector<int> vb[400001];
int n, f[5];

const int B = 420;

long long count_triples(std::vector<int> h) {
    n = h.size();
    vector<int> a(n), b(n), heavy;
    auto test = [&] (int i, int j, int k) {
        if (i == j || i == k || k == j) return false;
        int aa = min({i, j, k}), cc = max({i, j, k}), bb = aa ^ cc ^ i ^ j ^ k;
        if (h[aa] == cc - bb && h[bb] == cc - aa && h[cc] == bb - aa) return true;
        return false;
    };
    auto test2 = [&] (int i, int j, int k) {
        if (i == j || i == k || k == j) return false;
        int aa = min({i, j, k}), cc = max({i, j, k}), bb = aa ^ cc ^ i ^ j ^ k;
        if (h[aa] == cc - bb && h[bb] == cc - aa && h[cc] == bb - aa) {
            int cnt = 0;
            if (Fa[a[aa] + 200000] < B) cnt++;
            if (Fa[a[cc] + 200000] < B) cnt++;
            if (vb[b[aa]].size() < B) cnt++;
            if (vb[b[bb]].size() < B) cnt++;
            f[cnt]++;
            return true;
        }
        return false;
    };
    auto gentest = [&] (int i, int j, int k) {
        if (i == j || i == k || k == j) return false;
        vector<int> one = {abs(i - k), abs(i - j), abs(j - k)};
        vector<int> two = {h[i], h[j], h[k]};
        sort(one.begin(), one.end());
        sort(two.begin(), two.end());
        if (one == two) return true;
        return false;
    };
    for (int i = 0; i < n; i++) {
        for (int j : vector<int> {i - h[i], i + h[i]}) {
            if (j < 0 || j >= n || i == j) continue;
            for (int k : vector<int> {j - h[j], j + h[j], i - h[j], i + h[j]}) {
                if (k < 0 || k >= n || i == k || j == k) continue;
                if (gentest(i, j, k) && !test(i, j, k)) {
                    int ml = min({i, j, k}), mr = max({i, j, k});
                    ez.insert({ml, ml ^ mr ^ i ^ j ^ k, mr});
                }
            }
        }
    }
    int ans = ez.size();
    vector<bool> ok(n, false);
    for (int i = 0; i < n; i++) a[i] = h[i] - i, b[i] = h[i] + i, va[a[i]].push_back(i), vb[b[i]].push_back(i);
    for (auto& [k, v] : va) if (v.size() >= B) heavy.push_back(k);
    for (int i = 0; i < n; i++) if (va[a[i]].size() >= B && vb[b[i]].size() >= B) ok[i] = true;
    for (int i = -n; i < n; i++) Fa[i + 200000] = va[i].size();
    for (auto& x : heavy) for (auto& y : heavy) {
        if (x % 2 != y % 2) continue;
        for (auto& k : va[y]) {
            if (!ok[k]) continue;
            int i = -((y + x) / 2);
            if (i < 0 || i >= n || a[i] != x || !ok[i]) continue;
            for (int j : vector<int> {k - h[i], k + h[i]}) {
                if (j < 0 || j >= n || !ok[j]) continue;
                if (test(i, j, k)) ans++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (va[a[i]].size() >= B) continue;
        for (auto& j : va[a[i]]) {
            int k = j + h[i];
            if (k < 0 || k >= n) continue;
            if (i < j) test2(i, j, k);
        }
    }
    for (int j = 0; j < n; j++) {
        if (vb[b[j]].size() >= B) continue;
        for (auto& k : vb[b[j]]) {
            if (j >= k) continue;
            int i = j - h[k];
            if (i < 0 || i >= n) continue;
            test2(i, j, k);
        }
    }
    for (int k = 0; k < n; k++) {
        if (-a[k] < 0) continue;
        if (vb[-a[k]].size() >= B) continue;
        for (auto& i : vb[-a[k]]) {
            if (i >= k) continue;
            int j = i + h[k];
            if (j < 0 || j >= n) continue;
            if (i < j && j < k) test2(i, j, k);
        }
    }
    for (int i = 0; i < n; i++) {
        if (va[-b[i]].size() >= B) continue;
        for (auto& k : va[-b[i]]) {
            if (i >= k) continue;
            int j = i + h[k];
            if (j < 0 || j >= n) continue;
            if (i < j && j < k) test2(i, j, k);
        }
    }
    assert(f[2] % 2 == 0);
    assert(f[3] % 3 == 0);
    assert(f[4] % 4 == 0);
    ans += f[1] + f[2] / 2 + f[3] / 3 + f[4] / 4;
    return ans;
}

std::vector<int> construct_range(int M, int K) {
    return {1, 1, 1};
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 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