Submission #1250733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250733		NekoRolly	Triple Peaks (IOI25_triples)	C++20	75.29 / 100	893 ms	18248 KiB

triples

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

int n;
vector<int> h;

bool same(vector<int> a,vector<int> b){
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i=0; i<3; i++)
        if (a[i] != b[i]) return false;
    return true;
}

bool check(int i,int j,int k){
    bool flag = 0 <= i && i < j && j < k && k < n && same({k-i, k-j, j-i}, {h[i], h[j], h[k]});
    // if (flag) cout << i << " " << j << " " << k << " <-\n";
    // return 0 <= i && i < j && j < k && k < n && same({k-i, k-j, j-i}, {h[i], h[j], h[k]});
    return flag;
}

const int N = 2e5+4;;
vector<int> vals[2*N];

ll count_triples(vector<int> H){
    h = H;
    n = h.size();



    ll ans = 0;
    for (int i=0; i<n; i++){
        int l = i - h[i];
        int r = i + h[i];
        if (l >= 0){
            ans += check(l, l+h[l], i);
            if (l+h[l] != i-h[l])
                ans += check(l, i-h[l], i);
            if (h[l] != 2*h[i])
                ans += check(i-h[l], l, i);
        }
        if (r < n){
            ans += check(i, r-h[r], r);
            if (r-h[r] != i+h[r])
                ans += check(i, i+h[r], r);
        }

        vals[i + h[i]].push_back(i);
    }

    for (int val=1; val<2*n; val++){
        int sz = vals[val].size();
        if (sz == 0) continue;
        if (1ll*sz*sz <= n){ // *O(k*k)
            // cout << "caso 1 : val = " << val << " sz = " << sz << "\n";
            for (int j=0; j<sz; j++)
                for (int k=j+1; k<sz; k++){
                    int i = vals[val][j] + vals[val][k] - val;
                    ans += check(i, vals[val][j], vals[val][k]);
                }
        }
        else{ // *O(n)
            // cout << "caso 1 : val = " << val << " sz = " << sz << "\n";
            for (int i=0; i<n; i++){
                int j = i - h[i] + val;
                int k = i + h[i] + val;
                if (j%2 == 1 || k%2 == 1) continue;
                j /= 2, k /= 2;
                if (j < 0 || j >= n || k < 0 || k >= n) continue;
                if (j + h[j] != val || k + h[k] != val) continue;
                ans += check(i, j, k);
            }
        }
    }

    return ans;
}

vector<int> construct_range(int M, int K){
    vector<int> vec;
    int patron[] = {1, 1, 2}, p=0;
    while (vec.size() < M){
        vec.push_back(patron[p]);
        p = (p+1)%3;
    }
    return vec;
}

• 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