제출 #1254327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254327		nicolo_010	3개의 봉우리 (IOI25_triples)	C++20	0 / 100	246 ms	35560 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cout if (0) cout

ll fast_checker(v<int> &H) {
  int N = H.size();
  ll cnt = 0;
  rep(i, 0, N) {
    rep(j, i+1, N) {
      rep(k, j+1, N) {
        v<int> dis = {k-i, k-j, j-i};
        v<int> h = {H[i], H[j], H[k]};
        sort(dis.begin(), dis.end());
        sort(h.begin(), h.end());
        if (dis == h) {
          cout << "GOOD: " << i << " " << j << " " << k << endl;
          cnt++;
        }
      }
    }
  }
  return cnt;
}

ll count_triangles(v<v<int>> &edges, map<int, v<int>> &adj) {
  ll cnt = 0;
  for (auto x : edges) {
    int u = x[0];
    int v = x[1];
    if (adj[u].size() > adj[v].size()) {
      swap(u, v);
    }
    int i, j;
    i=j=0;
    while (i < (int)adj[u].size() && j<(int)adj[v].size()) {
      if (adj[u][i] == adj[v][j]) {
        cnt++;
        i++; j++;
      }
      else if (adj[u][i] > adj[v][j]) j++;
      else i++;
    }
  }
  return cnt/3;
}

long long count_triples(std::vector<int> H) {
  ll ans=0;
  int N = H.size();
  rep(i, 0, N) {
    if (H[i]+i < N) {
      int k = H[i]+i;
      if (k-H[k] >= 0) {
        int j = k-H[k];
        if (H[i] == k-i && H[k] == k-j && H[j] == j-i && (i != j && j != k && k != i) && !(H[i] == k-j && H[k] == j-i && H[j] == k-i) && (i < j && j < k)) {
          ans++;
          cout << "1" << endl;
          cout << i << " " << j << " " << k << endl;
        }
      }
      if (H[k]+i < N) {
        int j = H[k]+i;
        if (H[i] == k-i && H[k] == j-i && H[j] == k-j && (i != j && j != k && k != i) && !(H[i] == k-j && H[k] == j-i && H[j] == k-i) && (i < j && j < k)) {
          ans++;
          cout << "2" << endl;
          cout << i << " " << j << " " << k << endl;
        }
      }
    }
  }
  rep(k, 0, N) {
    if (k-H[k] >= 0) {
      int i = k-H[k];
      if (H[i]+i < N) {
        int j = H[i]+i;
        cout << i << " " << j << " " << k << " " << H[i] << " " << H[j] << " " << H[k] << endl;
        if (H[k] == k-i && H[i] == j-i && H[j] == k-j && (i != j && j != k && k != i) && !(H[i] == k-j && H[k] == j-i && H[j] == k-i) && (i < j && j < k)) {
          ans++;
          cout << i << " " << j << " " << k << endl;
        }
      }
      if (k-H[i] >= 0) {
        int j = k-H[i];
        if (H[k] == k-i && H[i] == k-j && H[j] == j-i && (i != j && j != k && k != i) && !(H[i] == k-j && H[k] == j-i && H[j] == k-i) && (i < j && j < k)) {
          ans++;
          cout << i << " " << j << " " << k << endl;
        }
      }
    }
  }
  rep(i, 0, N) {
    if (H[i]+i < N) {
      int j = H[i]+i;
      if (H[j]+i < N) {
        int k = H[j]+i;
        if (H[i] == j-i && H[k] == k-j && H[j] == k-i && (i != j && j != k && k != i) && !(H[i] == k-j && H[k] == j-i && H[j] == k-i) && (i < j && j < k)) {
          ans++; 
          cout << i << " " << j << " " << k << endl;
        }
      } 
    }
  }
  v<v<int>> edges;
  rep(i, 0, N) {
    edges.push_back({i-H[i], i+H[i]});
  }
  map<int, v<int>> adj;
  for (auto x : edges) {
    int u = x[0];
    int v = x[1];
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (auto &x : adj) {
    sort(x.second.begin(), x.second.end());
  }
  ans += count_triangles(edges, adj);
  cout << fast_checker(H) << " ";
  return ans;
}

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

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