Submission #1307815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307815		exoworldgd	Triple Peaks (IOI25_triples)	C++20	4.95 / 100	2094 ms	34792 KiB

triples

#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
ll count_triples(vector<int>h){
    int n=h.size(),sq=sqrt(n)+1;
    ll ans=0;
    vector<int>pos[n];
    for(int i=0;i<n;i++)pos[h[i]].push_back(i);
    for(int v=1;v<n;v++){
        if(v<=sq){
            for(int i:pos[v])for(int j:pos[v])if(i<j){
                int k=j+v;
                if(k<n){
                    vector<int>a={h[i],h[j],h[k]},b={j-i,k-i,k-j};
                    sort(a.begin(),a.end()),sort(b.begin(),b.end()),ans+=a==b;
                }
            }
        }else{
            for(int i=0;i<n;i++){
                int j=i+v,k=i+2*v;
                if(k<n){
                    vector<int>a={h[i],h[j],h[k]},b={v,2*v,v};
                    sort(a.begin(),a.end()),sort(b.begin(),b.end()),ans+=a==b;
                }
            }
        }
    }
    return ans;
}
vector<int>construct_range(int m,int k){
    vector<int>res;
    int pat[]={1,2,1,3,2,1,4,3,2,1},sz=10;
    for(int i=0;i<m;i++)res.push_back(pat[i%sz]);
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 2.6667 / 5
• Subtask 8: 1.24 / 5
• Subtask 9: 0.4996 / 5
• Subtask 10: 0.2143 / 5
• Subtask 11: 0.25 / 5
• Subtask 12: 0.0833 / 5