Submission #1331176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1331176		rainmar	Triple Peaks (IOI25_triples)	C++20	70 / 100	116 ms	16200 KiB

triples

#include "triples.h"

#include<bits/stdc++.h>
using namespace std;

long long count_triples(std::vector<int> H) {

  int n = H.size();

  //order is hi, hj, hk.
  
  //case one, hi is the largest value = k-i
  //so hi + i = k;
  //hk = H[k];

  long long sol = 0;

  for(int i = 0; i < n; i++) {
    

    if(i + H[i] < n) {
      int k = i + H[i];
      if(H[k] < H[i]) {
        int j = k - H[k];
        if(H[j] + H[k] == H[i]) {
          sol++;
        }

        if(H[k] * 2 != H[i]) { //so that we wont overcount. If i - x  - j - x - k then alr counted
          j = i + H[k];
          if(H[k] + H[j] == H[i]) {
            sol++;
          }
        }
      }
    }
    
    if(i - H[i] >= 0) {
      int k = i - H[i];
      if(H[k] < H[i]) {
        int j = k + H[k];
        if(H[k] + H[j] == H[i]) {
          sol++;
        }

        if(H[k] * 2 != H[i]) {
          j = i - H[k];
          if(H[j] + H[k] == H[i]) {
            sol++;
          }
        }
      }
    }
  }

  vector<int> b[2 * n + 1];
  for(int i = 0; i < n; i++) {
    b[n + H[i] - i].push_back(i);
  }

  int root = sqrt(n);

  for(int x = 1; x <= 2 * n; x++) {
    if(b[x].size() <= root) {
      for(int v1 = 0; v1 < b[x].size(); v1++) {
        int i = b[x][v1];
        for(int v2 = 0; v2 < v1; v2++) {
          int j = b[x][v2];
          int k = j + H[i];
          if (k < n && k > i){
            if (H[i] == (k - j) && H[j] == (k - i) && H[k] == (i - j)){
                sol++;
            }
          }
        }
      }
    } else {
      for (int k = 0; k < n; k++){
        int C = x - n;
        int sum = k - C;
        int diff = H[k];
        
        if (diff % 2 == sum % 2){
            int i = (sum - diff) / 2;
            int j = (sum + diff) / 2;
            
            if (0 <= i && i < n && 0 <= j && j < n && H[i] - i == C && H[j] - j == C){
                sol++;
            }
        }
      }
    }
  }

  for (int i = 0; i < n; i++){
      int j = i + H[i];
      if (j < n && H[j] > H[i]){
          int k = i + H[j];
          if (k < n){
              if (H[k] + H[i] == H[j] && H[k] != H[i]){
                  sol++;
              }
          }
      }
  }

  return sol;
}

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

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