| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1307822 | exoworldgd | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math,omit-frame-pointer")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#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();
set<set<int>>triples;
auto check=[&](int i,int j){
for(int id:{i,j})for(int dist:{h[i],h[j]})for(int k:{id-dist,id+dist})if(k>=0&&k<n&&k^i&&k^j){
vector<int>a={h[i],h[j],h[k]},b={abs(i-j),abs(i-k),abs(j-k)};
sort(a.begin(),a.end()),sort(b.begin(),b.end());
if(a==b)triples.insert({i,j,k});
}
};
for(int i=0;i<n;i++)for(int j:{i-h[i],i+h[i]})if(j>=0&&j<n)check(i,j);
int ans=triples.size();
map<int,vector<int>>d1,d2;
for(int i=0;i<n;i++)d1[i+h[i]].push_back(i),d2[i-h[i]].push_back(i);
for(int j=0,z;j<n;j++){
auto&x=d1[j+h[j]],&y=d2[j-h[j]];
if(x.size()<y.size())for(int k:x)z=k-h[j],ans+=(z>=0&&z<j&&j<k&&k<n&&h[z]==k-j&&h[j]==k-z&&h[k]==j-z&&h[z]^h[k]);
else for(int i:y)if(i<j)z=i+h[j],ans+=(i>=0&&i<j&&j<z&&z<n&&h[i]==z-j&&h[j]==z-i&&h[z]==j-i&&h[i]^h[z]);
}
return ans;
}
vector<int>construct_range(int M,int K){return{4,1,4,3,2,6,1};}