Submission #1257757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257757		mkkkkkkkk	Triple Peaks (IOI25_triples)	C++20	34.29 / 100	1279 ms	1864 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>


using namespace std;

map<int,int> mapa;

bool check(int i,int j,int k,vector<int>& H)
{
    if(i==j || i==k || j==k)
        return false;
    if(k<0 || k>=H.size())
        return false;

        if(mapa[k]==true)
            return false;

        vector<int> vec={i,j,k};
        sort(vec.begin(),vec.end());
    vector<int> vec1={abs(j-i),abs(k-i),abs(k-j)},vec2={H[i],H[j],H[k]};
    sort(vec2.begin(),vec2.end());
    sort(vec1.begin(),vec1.end());
    if(vec1==vec2)
    {
        mapa[k]=true;
        return true;

    }
    else
        return false;
}

long long count_triples(vector<int> H) {
  if(H.size()<=2000)
  {
      long long cnt=0;
      for(int i=0;i<H.size();i++)
      {
          for(int j=i+1;j<H.size();j++)
          {
              mapa.clear();
                cnt+=check(i,j,j+H[i],H)+check(i,j,i+H[i],H)+check(i,j,j-H[i],H)+check(i,j,i-H[i],H);
                cnt+=check(i,j,j+H[j],H)+check(i,j,i+H[j],H)+check(i,j,j-H[j],H)+check(i,j,i-H[j],H);
          }
      }
      return cnt/3;
  }
  else
  {
      long long cnt=0;
        for(int i=2;i<H.size();i++)
        {
            if(i-H[i]>=0)
            {
            mapa.clear();
            cnt+=check(i,i-H[i],i-H[i]+H[i-H[i]],H);
            cnt+=check(i,i-H[i],i-H[i-H[i]],H);
            }
        }
        return cnt;
  }
}

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

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