Submission #1263841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263841		SkillIssueWAGuy	Triple Peaks (IOI25_triples)	C++20	41.53 / 100	2096 ms	50260 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N;
vector<int> H;
vector<vector<int>> F(0);
bool _L (vector<int> a, vector<int> b){
  for (int i = 0; i < 3; i++){
    if (a[i] != b[i]) return a[i] < b[i];
  }
  return false;
};
bool _E (vector<int> a, vector<int> b){
  for (int i = 0; i < 3; i++) if (a[i] != b[i]) return false;
  return true;
}
vector<int> _MK (int a, int b, int c){
  vector<int> o = {a, b, c};
  sort(o.begin(), o.end());
  return o;
}
void _CH (vector<int> a){
  auto p = _MK (abs(a[0] - a[1]), abs(a[1] - a[2]), abs(a[0] - a[2]));
  for (int i = 0; i < 3; i++) if (a[i] < 0 || a[i] >= N) return;
  auto q = _MK (H[a[0]], H[a[1]], H[a[2]]);
  if (_E(p, q)) F.push_back(a);
}
long long count_triples(std::vector<int> h) {
  N = h.size();
  H = h;
  bool st = true;
  for (int i = 0; i < N-1; i++) {
    if (H[i+1] < H[i]) st = false;
  }
  for (int i = 0; i < N; i++) {
    // forward
    int p = i + H[i];
    if (p < N) {
      _CH(_MK(i, p, p+H[p]));
      _CH(_MK(i, p, p-H[p]));
      _CH(_MK(i, p, i+H[p]));
      _CH(_MK(i, p, i-H[p]));
    }
    // backward
    p = i - H[i];
    if (p >= 0) {
      _CH(_MK(i, p, p+H[p]));
      _CH(_MK(i, p, p-H[p]));
      _CH(_MK(i, p, i+H[p]));
      _CH(_MK(i, p, i-H[p]));
    }
    if (st) continue;
    for (int j = i - H[i] + 1; j < i; j++){
      _CH({j, i, j + H[i]});
    }
  }


  // make return
  sort(F.begin(), F.end(), _L);
  int out=  F.size();
  for (int i = 1; i < F.size(); i++) {
    if (_E(F[i], F[i-1])) out--;
  }
  return out;
}

std::vector<int> construct_range(int M, int K) {
  vector<int> out;
  vector<int> cur = {1,2,1,3};
  for (int i =0 ; i < M; i++){
    out.push_back(cur[i%4]);
  }
  return out;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 3.6667 / 5
• Subtask 8: 1.555 / 5
• Subtask 9: 0.6247 / 5
• Subtask 10: 0.2678 / 5
• Subtask 11: 0.3125 / 5
• Subtask 12: 0.1042 / 5