Submission #1252679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252679		Clan328	Triple Peaks (IOI25_triples)	C++20	40.29 / 100	465 ms	1984 KiB

triples

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

using namespace std;

long long count_triples(std::vector<int> h) {
  int n = h.size();

  long long res = 0;

  bool nonDec = true;
  for (int i = 0; i < n-1; i++) nonDec &= h[i] <= h[i+1];

  if (nonDec) {
    for (int i = 0; i < n; i++) {
      bool already = false;
      if (h[i]+i < n && h[i]+i-h[h[i]+i] >= 0 && h[i]+i-h[h[i]+i] < i) {
        vector<int> a = {h[i], h[h[i]+i], h[h[i]+i-h[h[i]+i]]};
        vector<int> b = {h[i], h[h[i]+i]-h[i], h[h[i]+i]};
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        if (a == b) {
          already = true;
          res++;
        }
      }

      if (i-h[i] >= 0 && i+h[i-h[i]] < n && i+h[i-h[i]] > i) {
        vector<int> a = {h[i], h[i+h[i-h[i]]], h[i-h[i]]};
        vector<int> b = {h[i], h[i-h[i]], h[i]+h[i-h[i]]};
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        if (a == b && (!already || h[i]+i-h[h[i]+i] != i-h[i] || i+h[i-h[i]] != h[i]+i)) res++;
      }
    }
  } else if (n <= 2000) {
    for (int i = 0; i < n; i++) {
      for (int j = i+1; j < n; j++) {
        if (h[i]+j < n) {
          vector<int> a = {h[i], h[j], h[h[i]+j]};
          vector<int> b = {j-i, h[i], h[i]+j-i};
          sort(a.begin(), a.end());
          sort(b.begin(), b.end());

          if (a == b) res++;
        }

        if (h[j]+j < n && h[i] != h[j]) {
          vector<int> a = {h[i], h[j], h[h[j]+j]};
          vector<int> b = {j-i, h[j], h[j]+j-i};
          sort(a.begin(), a.end());
          sort(b.begin(), b.end());
          
          if (a == b) res++;
        }

        if (abs(h[i]-h[j])+j < n && h[i] != abs(h[i]-h[j]) && h[j] != abs(h[i]-h[j])) {
          vector<int> a = {h[i], h[j], h[abs(h[i]-h[j])+j]};
          vector<int> b = {j-i, abs(h[i]-h[j]), abs(h[i]-h[j])+j-i};
          sort(a.begin(), a.end());
          sort(b.begin(), b.end());
          
          if (a == b) res++;
        }
      }
    }
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = i+1; j < n && j < i+20; j++) {
        if (h[i]+j < n) {
          vector<int> a = {h[i], h[j], h[h[i]+j]};
          vector<int> b = {j-i, h[i], h[i]+j-i};
          sort(a.begin(), a.end());
          sort(b.begin(), b.end());

          if (a == b) res++;
        }

        if (h[j]+j < n && h[i] != h[j]) {
          vector<int> a = {h[i], h[j], h[h[j]+j]};
          vector<int> b = {j-i, h[j], h[j]+j-i};
          sort(a.begin(), a.end());
          sort(b.begin(), b.end());
          
          if (a == b) res++;
        }

        if (abs(h[i]-h[j])+j < n && h[i] != abs(h[i]-h[j]) && h[j] != abs(h[i]-h[j])) {
          vector<int> a = {h[i], h[j], h[abs(h[i]-h[j])+j]};
          vector<int> b = {j-i, abs(h[i]-h[j]), abs(h[i]-h[j])+j-i};
          sort(a.begin(), a.end());
          sort(b.begin(), b.end());
          
          if (a == b) res++;
        }
      }
    }
  }

  return res;
}

std::vector<int> construct_range(int M, int K) {
  vector<int> ans(M);
  for (int i = 0; i < M; i++) {
    if (i % 3 <= 1) ans[i] = 1;
    else ans[i] = 2;
  }

  return ans;
}

• 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 / 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