Submission #1257326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257326		medmdg	Triple Peaks (IOI25_triples)	C++20	45.29 / 100	2095 ms	2736 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> H;
ll n;
bool check(ll i,ll j,ll k){
  if(i<0||j<0||k<0||i>=n||j>=n||k>=n)return 0;
  ll s1[3],s2[3];
  s1[0]=(abs(j-i));
  s1[1]=(abs(k-i));
  s1[2]=(abs(j-k));
  sort(s1,s1+3);
  if(s1[0]==0)return 0;
  s2[0]=(H[i]);
  s2[1]=(H[j]);
  s2[2]=(H[k]);
  sort(s2,s2+3);
  return s1[0]==s2[0]&&s1[1]==s2[1]&&s1[2]==s2[2];
}
ll sub4(){
  ll ans=0;
  for(int i=n-1;i>1;i--){
    ll x2=i-H[i];
    if(x2<0)continue;
    ll x3=x2+H[x2],x4=i-H[x2];
    if(x3<i && i-x3==H[x3])ans++;
    if(x3!=x4)
    if(x4>x2 && x4-x2==H[x4])ans++;
  }
  return ans;
}
ll sub2(){
  ll ans=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<=i+20;j++){
      for(int k=j+1;k<n&&k<i+20;k++){
        ans+=check(i,j,k);
      }
    }
  }
  return ans;
}
ll sub3(){
  ll ans=0;
  for(ll i=0;i<n;i++){
    //Check M a b
    while(1){
      ll x2=i+H[i];
      if(x2>=n)break;
      ll x3=x2-H[x2],x4=i+H[x2];
      if(x3>i && x3-i==H[x3])ans++;
      if(x3!=x4)
      if(x4<x2 && x2-x4==H[x4])ans++;
      break;
    }
    //check a b M
    while(1){
      ll x2=i-H[i];
      if(x2<0)break;
      ll x3=x2+H[x2],x4=i-H[x2];
      if(x3<i && i-x3==H[x3])ans++;
      if(x3!=x4)
      if(x4>x2 && x4-x2==H[x4])ans++;
      break;
    }
    //check a M b
    ll l=max(0LL,i-H[i]+1);
    ll r=min(i,n-H[i]);
    for(int j=l;j<r;j++){
      ll x3=j+H[i];
      if(H[j]==i-j&&H[x3]==x3-i)ans++;
      else if(H[x3]==i-j&&H[j]==x3-i)ans++;
    }
  }
  return ans;
}
ll count_triples(vector<int> h) {
  n=h.size();

  H=h;
  return sub3();
}

vector<int> construct_range(int M, int K) {
  vector<int> a;
  for(int i=0;i<M;i++){
    if(i%3)a.push_back(1);
    else a.push_back(2);
  }
  return a;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 16 / 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