| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1285790 | eri16 | Triple Peaks (IOI25_triples) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "triples.h"
using namespace std;
long long solve(int hi,int hj, int ht, int i, int j, int t){
vector <int> v,v1;
v.push_back(hi);
v.push_back(hj);
v.push_back(ht);
v1.push_back(j-i);
v1.push_back(t-j);
v1.push_back(t-i);
sort(v.begin(),v.end());
sort(v1.begin(),v1.end());
int qwe=1;
for (int zz=0; zz<3; zz++){
if (v[zz]!=v1[zz]){qwe=0;}
}
return qwe;
}
long long count_triples(vector<int> h) {
long long n=h.size();
long long ans=0;
long long maxh=0;
for (int i=0; i<n; i++){
maxh=max(maxh,h[i]);
}
if (n<=2000){
for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
int ds1=j-i;
if (ds1==h[j]){
int ps1,ps2,ps3,ps4,ds2;
ds2=h[i];
ps1=i-ds2;
ps2=j-ds2;
ps3=i+ds2;
ps4=j+ds2;
if (ps1>=0 && ps1<n){ans+=solve(h[i],h[j],h[ps1],i,j,ps1);}
if (ps2>=0 && ps2<n){ans+=solve(h[i],h[j],h[ps2],i,j,ps2);}
if (ps3>=0 && ps3<n){ans+=solve(h[i],h[j],h[ps3],i,j,ps3);}
if (ps4>=0 && ps4<n){ans+=solve(h[i],h[j],h[ps4],i,j,ps4);}
}
else if (ds1==h[i]){
int ps1,ps2,ps3,ps4,ds2;
ds2=h[j];
ps1=i-ds2;
ps2=j-ds2;
ps3=i+ds2;
ps4=j+ds2;
if (ps1>=0 && ps1<n){ans+=solve(h[i],h[j],h[ps1],i,j,ps1);}
if (ps2>=0 && ps2<n){ans+=solve(h[i],h[j],h[ps2],i,j,ps2);}
if (ps3>=0 && ps3<n){ans+=solve(h[i],h[j],h[ps3],i,j,ps3);}
if (ps4>=0 && ps4<n){ans+=solve(h[i],h[j],h[ps4],i,j,ps4);}
}
else if(ds1+min(h[i],h[j])==max(h[i],h[j])){
int ps1,ps2;
ps1=i-min(h[i],h[j]);
ps2=j+min(h[i],h[j]);
if (ps1>=0 && ps1<n){ans+=solve(h[i],h[j],h[ps1],i,j,ps1);}
if (ps2>=0 && ps2<n){ans+=solve(h[i],h[j],h[ps2],i,j,ps2);}
}
}
}
return(ans);
}
else if(maxh<=10){
for (int i=0; i<n; i++){
for (int j=i+1; j<n && j<=i+10; j++){
for (int t=j+1; t<n && t<=j+10; t++){
vector <int> v,v1;
v.push_back(h[i]);
v.push_back(h[j]);
v.push_back(h[t]);
v1.push_back(j-i);
v1.push_back(t-j);
v1.push_back(t-i);
sort(v.begin(),v.end());
sort(v1.begin(),v1.end());
int qwe=1;
for (int zz=0; zz<3; zz++){
if (v[zz]!=v1[zz]){qwe=0;}
}
ans+=qwe;
}
}
}
return(ans);
}
else{
for (int i=0; i<n; i++){
long long t=i+h[i];
long long j=t-h[t];
ans+=solve(h[i],h[j],h[t],i,j,t);
}
}
}
vector<int> construct_range(int M, int K) {vector <int> vv;return(vv);}
/*
int main(){
cout << count_triples({4, 1, 4, 3, 2, 6, 1});
}
*/
//