제출 #1252790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252790		Clan328	3개의 봉우리 (IOI25_triples)	C++20	75.57 / 100	128 ms	23464 KiB

triples

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

using namespace std;

struct Triplet {
  int i, j, k;
};

int n;
map<pair<pair<int, int>, int>, int> mapper;
vector<int> h;

bool check(int i, int j, int k) {
  if (i < 0 || j < 0 || k < 0 || i >= n || j >= n || k >= n) return 0;
  if (!(i < j && j < k)) return 0;

  if (mapper.count({{i, j}, k})) return 0;

  vector<int> a = {h[i], h[j], h[k]};
  vector<int> b = {j-i, k-j, k-i};
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  if (a == b) {
    mapper[{{i, j}, k}] = true;
    return 1;
  }
  return 0;
}

long long count_triples(std::vector<int> H) {
  h = H;
  n = h.size();
  mapper = map<pair<pair<int, int>, int>, int>();

  long long res = 0;

  for (int i = 0; i < n; i++) {
    if (i+h[i] < n) res += check(i+h[i]-h[i+h[i]], i, i+h[i]);
    if (i+h[i] < n) res += check(i-h[i+h[i]], i, i+h[i]);
    if (i-h[i] >= 0) res += check(i-h[i], i, i-h[i]+h[i-h[i]]);
    if (i-h[i] >= 0) res += check(i-h[i], i, i+h[i-h[i]]);
  }
  for (int i = 0; i < n; i++) {
    int j = i+h[i];
    if (j >= n) continue;
    int k = i + h[j];
    if (k >= n) continue;
    if (k <= j) continue;
    if (h[i] == h[k]) continue;

    vector<int> a = {h[i], h[j], h[k]};
    vector<int> b = {j-i, k-j, k-i};
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

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

  // for (int i = 0; i < n; i++) {
  //   for (int j = i+1; j < n; j++) {
  //     for (int k = j+1; k < n; k++) {
  //       res += h[k] == j-i && h[i] == k-j && h[j] == k-i;
  //     }
  //   }
  // }

  vector<vector<int>> groups(n);
  for (int i = 0; i < n; i++) {
    if (i-h[i] >= 0) groups[i-h[i]].push_back(i);
  }

  for (int i = 0; i < n; i++) {
    if (i+h[i] >= n) continue;
    for (auto k : groups[i+h[i]]) {
      res += h[h[k]+i] == k-i;
    }
  }

  // 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> tmp = {8, 3, 1, 2, 1, 4, 3, 2};
  vector<int> ans(M);
  for (int i = 0; i < M; i++) {
    ans[i] = tmp[i%8];
  }

  return ans;
}

• 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: 3 / 5
• Subtask 8: 1.395 / 5
• Subtask 9: 0.5624 / 5
• Subtask 10: 0.2411 / 5
• Subtask 11: 0.2812 / 5
• Subtask 12: 0.0937 / 5