Submission #1251810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251810		Lithanium	Triple Peaks (IOI25_triples)	C++20	57.01 / 100	2130 ms	778156 KiB

triples

#pragma GCC optimize("Ofast,unroll-loops")

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

using ll = long long;

mt19937_64 rd(time(0));

ll Hash1[200005];
ll Hash2[200005];

vector<int> construct_range(int M, int K) {
    M /= 6;
    M *= 6;
    vector<int> ans;
    for (int i = 0; i < M; i += 6) {
        for (int j:{3, 4, 2, 1, 1, 3}) ans.push_back(j);
    }
    return ans;
}

gp_hash_table<ll, bool> all;
vector<int> H;

void check(int a, int b, int c) {
    if (c < 0 or c >= H.size()) return;
    if (a == b or a == c or b == c) return;
    array<int, 3> h = {H[a], H[b], H[c]};
    array<int, 3> diff = {abs(a-b), abs(a-c), abs(b-c)};
    sort(h.begin(), h.end());
    sort(diff.begin(), diff.end());
    if (h == diff) {
        all[Hash1[a]^Hash1[b]^Hash1[c]] = 1;
    }
}

vector<int> adj[400005];
gp_hash_table<int, __gnu_pbds::null_type> big[400005];
int from[400005];
gp_hash_table<int, int> bruh[400005];
vector<int> cc;

ll triangles() {
    int N = cc.size();
    vector<int> order;
    for (int i = 0; i < N; i ++) order.push_back(i);
    sort(order.begin(), order.end(), [](const int a, const int b) {
        return adj[a].size() < adj[b].size();
    });
    for (int i = 0; i < N; i ++) for (int j:adj[i]) if (make_pair(i, adj[i].size()) < make_pair(j, adj[j].size())) {
        big[i].insert(j);
    }
    ll num = 0;
    for (int ii = 0; ii < N; ii ++) {
        int i = order[ii];
        for (int j:big[i]) {
            for (int k:big[j]) if (big[i].find(k) != big[i].end()) {
                // cout << i << " " << j << " " << k << "\n";
                // cout << bruh[i][j] << " " << bruh[i][k] << " " << bruh[j][k] << "\n";
                check(bruh[i][j], bruh[i][k], bruh[j][k]);
                num ++;
            }
        }
    }
    return num;
}

ll count_triples(vector<int> h) {
    ::H = h;
    int N = H.size();
    for (int i = 0; i < N; i ++) Hash1[i] = rd(), Hash2[i] = rd();
    for (int i = 0; i < N; i ++) {
        // Normal case:
        // Edge with length H[i] connects from i
        int p1 = i, p2 = i - H[i];
        if (p2 >= 0) {
            check(p1, p2, p1 - H[p2]);
            check(p1, p2, p1 + H[p2]);
            check(p1, p2, p2 - H[p2]);
            check(p1, p2, p2 + H[p2]);
        }
        p1 = i, p2 = i + H[i];
        if (p2 < N) {
            check(p1, p2, p1 - H[p2]);
            check(p1, p2, p1 + H[p2]);
            check(p1, p2, p2 - H[p2]);
            check(p1, p2, p2 + H[p2]);
        }
    }
    // count triangles in a graph
    for (int i = 0; i < N; i ++) {
        cc.push_back(i - H[i]);
        cc.push_back(i + H[i]);
    }
    sort(cc.begin(), cc.end());
    cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
    for (int i = 0; i < N; i ++) {
        int a = lower_bound(cc.begin(), cc.end(), i - H[i]) - cc.begin();
        int b = lower_bound(cc.begin(), cc.end(), i + H[i]) - cc.begin();
        bruh[a][b] = bruh[b][a] = i;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    triangles();
    return (ll)all.size();
}

• 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: 0 / 19
• Subtask 7: 3.3333 / 5
• Subtask 8: 1.45 / 5
• Subtask 9: 0.583 / 5
• Subtask 10: 0.25 / 5
• Subtask 11: 0.2917 / 5
• Subtask 12: 0.0972 / 5