Submission #1249457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249457		_is_this_fft_	Triple Peaks (IOI25_triples)	C++20	70 / 100	170 ms	18756 KiB

triples

#include "triples.h"
#include <map>

using namespace std;

typedef long long ll;

// a  b  c

// type 0:
//  c  a
//   b

// type 1:
//  a  b
//   c

// type 2:
//  a  c
//   b

// type 3:
//  b  a
//   c

// type 4:
//  b  c
//   a

// type 5:
//  c  b
//   a

void try_add_triple (int i, int j, int k, int type, ll &ans, const vector<int> &H) {
  int n = H.size();
  if (i < 0 || j < 0 || k < 0)
    return;
  if (i >= n || j >= n || k >= n)
    return;
  
  if (j - i == H[k] && k - j == H[i] && k - i == H[j]) {
    if (type == 0)
      ans++;
    
    return;
  }

  if (j - i == H[i] && k - j == H[j] && k - i == H[k]) {
    if (type == 1)
      ans++;

    return;
  }

  if (j - i == H[i] && k - j == H[k] && k - i == H[j]) {
    if (type == 2)
      ans++;

    return;
  }

  if (j - i == H[j] && k - j == H[i] && k - i == H[k]) {
    if (type == 3)
      ans++;

    return;
  }

  if (j - i == H[j] && k - j == H[k] && k - i == H[i]) {
    if (type == 4)
      ans++;

    return;
  }

  if (j - i == H[k] && k - j == H[j] && k - i == H[i]) {
    if (type == 5)
      ans++;

    return;
  }
}

const int SQR = 444;

ll count_triples (vector<int> H) {
  int n = H.size();
  ll ans = 0;

  // type 0
  map<int, vector<int>> groups;
  for (int i = 0; i < n; i++) {
    groups[i - H[i]].push_back(i);
  }

  for (auto pr : groups) {
    int key = pr.first;
    auto group = pr.second;
    if (group.size() < SQR) {
      // small group
      // try all possibilities
      for (int a = 0; a < (int) group.size(); a++) {
        int i = group[a];
        for (int b = a + 1; b < (int) group.size(); b++) {
          int j = group[b];
          int k = j + H[i];
          try_add_triple(i, j, k, 0, ans, H);
        }
      }
    } else {
      vector<int> in_group (n);
      for (int u : group)
        in_group[u] = 1;
      
      // big group
      // iterate over the array
      for (int k = 0; k < n; k++) {
        if ((key + k + H[k]) % 2 == 0) {
          int j = (key + k + H[k]) / 2;
          if (0 <= j && j < n) {
            int i = k - H[j];
            if (i < j && j < k)
              try_add_triple(i, j, k, 0, ans, H);
          }
        }
      }
    }
  }

  // type 1
  for (int i = 0; i < n; i++) {
    int j = i + H[i];
    if (j < n) {
      int k = j + H[j];
      try_add_triple(i, j, k, 1, ans, H);
    }
  }

  // type 2
  for (int i = 0; i < n; i++) {
    int j = i + H[i];
    if (j < n) {
      int k = i + H[j];
      try_add_triple(i, j, k, 2, ans, H);
    }
  }

  // type 3
  for (int j = 0; j < n; j++) {
    int i = j - H[j];
    if (i >= 0) {
      int k = j + H[i];
      try_add_triple(i, j, k, 3, ans, H);
    }
  }

  // type 4
  for (int j = 0; j < n; j++) {
    int i = j - H[j];
    if (i >= 0) {
      int k = i + H[i];
      try_add_triple(i, j, k, 4, ans, H);
    }
  }

  // type 5
  for (int j = 0; j < n; j++) {
    int k = j + H[j];
    if (k < n) {
      int i = j - H[k];
      try_add_triple(i, j, k, 5, ans, H);
    }
  }

  return ans;
}

vector<int> construct_range (int, int) { }

Compilation message (stderr)

triples.cpp: In function 'std::vector<int> construct_range(int, int)':
triples.cpp:178:42: warning: no return statement in function returning non-void [-Wreturn-type]
  178 | vector<int> construct_range (int, int) { }
      |                                          ^

• 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