Submission #1302482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302482		regulardude6	Triple Peaks (IOI25_triples)	C++20	13.65 / 100	82 ms	37284 KiB

triples

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

static inline bool is_mythical(const vector<int>& H, int i, int j, int k){
    int a = j - i;
    int b = k - j;
    int c = k - i;
    array<int,3> d = {a,b,c};
    array<int,3> h = {H[i], H[j], H[k]};
    sort(d.begin(), d.end());
    sort(h.begin(), h.end());
    return d == h;
}

long long count_triples(vector<int> H){
    int N = (int)H.size();
    unordered_set<unsigned long long> seen;
    seen.reserve((size_t)N * 8);

    auto key = [&](int i,int j,int k)->unsigned long long{
        return ( (unsigned long long)i << 42 ) ^ ( (unsigned long long)j << 21 ) ^ (unsigned long long)k;
    };

    auto try_add = [&](int i,int j,int k){
        if(i < 0 || j < 0 || k < 0) return;
        if(i >= N || j >= N || k >= N) return;
        if(!(i < j && j < k)) return;
        if(!is_mythical(H, i, j, k)) return;
        seen.insert(key(i,j,k));
    };

    unordered_set<unsigned long long> usedPairs;
    usedPairs.reserve((size_t)N * 4);

    auto pairkey = [&](int i,int j)->unsigned long long{
        return ( (unsigned long long)i << 21 ) ^ (unsigned long long)j;
    };

    auto process_pair = [&](int i, int j, int a){
        if(!(0 <= i && i < j && j < N)) return;
        unsigned long long pk = pairkey(i,j);
        if(usedPairs.find(pk) != usedPairs.end()) return;
        usedPairs.insert(pk);

        int hi = H[i], hj = H[j];

        if(hi > a){
            int b = hi - a;
            try_add(i, j, j + b);
        }
        if(hj > a){
            int b = hj - a;
            try_add(i, j, j + b);
        }

        {
            int b = hi;
            try_add(i, j, j + b);
        }
        {
            int b = hj;
            try_add(i, j, j + b);
        }
    };

    for(int u=0;u<N;u++){
        int d = H[u];
        int v = u + d;
        if(v < N) process_pair(u, v, d);
    }
    for(int u=0;u<N;u++){
        int d = H[u];
        int i = u - d;
        if(i >= 0) process_pair(i, u, d);
    }

    return (long long)seen.size();
}

vector<int> construct_range(int M, int K){
    int N = max(3, min(M, 200000));
    vector<int> H(N, 1);
    for(int i=0;i<N;i++){
        H[i] = min(N-1, max(1, (i%2 ? 1 : 2)));
    }
    return H;
}

• 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: 1.5 / 5
• Subtask 8: 0.6225 / 5
• Subtask 9: 0.2499 / 5
• Subtask 10: 0.1071 / 5
• Subtask 11: 0.125 / 5
• Subtask 12: 0.0417 / 5