Submission #1253845

#TimeUsernameProblemLanguageResultExecution timeMemory
1253845TINTriple Peaks (IOI25_triples)C++20
41.53 / 100
55 ms1956 KiB
#include "triples.h" #include <algorithm> #include <set> long long count_triples(std::vector<int> H) { int N = (int) H.size(); if (N <= 100) { long long ans = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { for (int k = j + 1; k < N; k++) { if (H[i] == j - i && H[j] == k - j && H[k] == k - i) ++ans; else if (H[i] == j - i && H[k] == k - j && H[j] == k - i) ++ans; else if (H[j] == j - i && H[i] == k - j && H[k] == k - i) ++ans; else if (H[j] == j - i && H[k] == k - j && H[i] == k - i) ++ans; else if (H[k] == j - i && H[i] == k - j && H[j] == k - i) ++ans; else if (H[k] == j - i && H[j] == k - j && H[i] == k - i) ++ans; } } } return ans; } int mx = 0; for (int i = 0; i < N; i++) mx = std::max(mx, H[i]); if (mx <= 10) { long long ans = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < std::min(N, i + mx); j++) { for (int k = j + 1; k < std::min(N, j + mx); k++) { if (H[i] == j - i && H[j] == k - j && H[k] == k - i) ++ans; else if (H[i] == j - i && H[k] == k - j && H[j] == k - i) ++ans; else if (H[j] == j - i && H[i] == k - j && H[k] == k - i) ++ans; else if (H[j] == j - i && H[k] == k - j && H[i] == k - i) ++ans; else if (H[k] == j - i && H[i] == k - j && H[j] == k - i) ++ans; else if (H[k] == j - i && H[j] == k - j && H[i] == k - i) ++ans; } } } return ans; } if (N <= 2000) { long long ans = 0; std::set<int> s; for (int k = 0; k < N; k++) { for (int i = 0; i < k; i++) { s.clear(); int j; // i < j < k // H[i] = j - i j = i + H[i]; if (i < j && j < k) { if (H[i] == j - i && H[j] == k - j && H[k] == k - i) ++ans, s.insert(j); else if (H[i] == j - i && H[k] == k - j && H[j] == k - i) ++ans, s.insert(j); } // H[i] = k - j j = k - H[i]; if (i < j && j < k && s.find(j) == s.end()) { if (H[j] == j - i && H[i] == k - j && H[k] == k - i) ++ans, s.insert(j); else if (H[k] == j - i && H[i] == k - j && H[j] == k - i) ++ans, s.insert(j); } // H[i] = k - i if (i + H[i] == k) { // H[k] = k - j j = k - H[k]; if ((i < j && j < k) && (H[j] == j - i) && (s.find(j) == s.end())) ++ans, s.insert(j); // H[k] = j - i j = i + H[k]; if ((i < j && j < k) && (H[j] == k - j) && (s.find(j) == s.end())) ++ans, s.insert(j); } } } return ans; } bool ok = true; for (int i = 1; i < N; i++) if (H[i] < H[i - 1]) ok = false; if (ok) { long long ans = 0; std::set<int> s; for (int k = 0; k < N; k++) { int i = k - H[k]; if (i < 0) continue; s.clear(); // H[i] = k - j || H[i] = j - i int j; // H[i] = k - j j = k - H[i]; if (i < j && j < k && H[j] == j - i && s.find(j) == s.end()) ++ans, s.insert(j); // H[i] = j - i j = i + H[i]; if (i < j && j < k && H[j] == k - j && s.find(j) == s.end()) ++ans, s.insert(j); } return ans; } return 0LL; } std::vector<int> construct_range(int M, int K) { std::vector<int> H(M); for (int i = 0; i < M; i++) { H[i] = 1; if (i % 4 == 2) H[i] = 2; if (i % 4 == 3) H[i] = 3; } return H; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...