Submission #1256723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256723		medmdg	Triple Peaks (IOI25_triples)	C++20	18 / 100	15 ms	2628 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(){
  return 0;
}
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++){
      ans+=check(j,i,j+H[i]);
    }
  }
  return ans;
}
ll count_triples(vector<int> h) {
  n=h.size();

  H=h;
  if(n<2001)return sub3();
  else return 0;
}

std::vector<int> construct_range(int M, int K) {
  return {1, 1, 1};
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5