Submission #1250593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250593		countless	Triple Peaks (IOI25_triples)	C++20	75.29 / 100	1109 ms	210680 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O5")

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

inline void bubble(vector<int> &a) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2-i; j++) {
            if (a[j] > a[j+1]) swap(a[j], a[j+1]);
        }
    }
}

vector<tuple<int, int, int>> stuff;

inline void add(int i, int j, int k, map<tuple<int, int, int>, bool> &mp, vector<int> &H, bool ok = true) {
    if (i == j or j == k or i == k) return;
    vector<int> a = {i, j, k};
    sort(a.begin(), a.end());
    // bubble(a);
    if (!ok) {
        vector<int> b = {a[2]-a[0], a[2]-a[1], a[1]-a[0]};
        sort(b.begin(), b.end());
        // bubble(b);
        vector<int> c = {H[i], H[j], H[k]};
        sort(c.begin(), c.end());
        // bubble(c);
        if (b != c) return;
    }

    // mp[{a[0], a[1], a[2]}] = true;
    stuff.emplace_back(a[0], a[1], a[2]);
    return;
}

long long count_triples(vector<int> H) {
    const int SHIFT = 2e5+21;
    int n = H.size();
    map<tuple<int, int, int>, bool> mp;
    vector<vector<int>> diff(SHIFT * 2);

    for (int i = 0; i < n; i++) {
        diff[H[i]-i+SHIFT].push_back(i);
        int j = H[i]+i;
        if (j >= n) continue;
        int d = j-i;
        int t = (d == H[i] ? H[j] : H[i]);
        int w, x, y, z;
        w = i-t, x = i+t;
        y = j-t, z = j+t;

        if (w >= 0 and H[w] == abs(j-w)) add(i, j, w, mp, H);
        if (x < n and H[x] == abs(j-x)) add(i, j, x, mp, H);
        if (y >= 0 and H[y] == abs(i-y)) add(i, j, y, mp, H);
        if (z < n and H[z] == abs(i-z)) add(i, j, z, mp, H);
    }

    int CB = cbrt(n);
    int SQ = 700;
    for (int k = 0; k < 2 * SHIFT; k++) {
        auto &v = diff[k];
        if (v.size() <= 1) continue;
        int di = k - SHIFT;
        if (v.size() <= SQ) {
            for (auto &i : v) {
                for (auto &j : v) {
                    if (j <= i) continue;
                    int d = j-i;
                    int t = min(H[i], H[j]);
                    int x, y;
                    x = i-t, y = j+t;
                    if (x >= 0 and H[x] == d) add(i, j, x, mp, H);
                    if (y < n and H[y] == d) add(i, j, y, mp, H);
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                int j = (i-H[i]-di)/2;
                if (j < 0 or j >= n) continue;
                int t = min(H[i], H[j]);
                int x, y;
                x = i-t, y = j+t;
                if (x >= 0) add(i, j, x, mp, H, false);
                if (y < n) add(i, j, y, mp, H, false);
            }
        }
    }

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

    return stuff.size();
}

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

• 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: 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