Submission #1250666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250666		NekoRolly	Triple Peaks (IOI25_triples)	C++20	40.29 / 100	2095 ms	2632 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;
}

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

    bool not_desc = true;
    for (int i=0; i+1<n; i++)
        if (h[i] > h[i+1])
            not_desc = false;

    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 (r < n){
            ans += check(i, r-h[r], r);
            if (r-h[r] != i+h[r])
                ans += check(i, i+h[r], r);
        }
        if (!not_desc){
            l = max(l+1, 0);
            r = min(r-1, n-1);
            for (int j=l; j+h[i]<=r; j++)
                ans += check(j, i, j+h[i]);
        }
    }

    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: 0 / 16
• Subtask 6: 0 / 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