Submission #1249896

#TimeUsernameProblemLanguageResultExecution timeMemory
1249896kduckpTriple Peaks (IOI25_triples)C++20
15.99 / 100
2095 ms20336 KiB
#include "triples.h" #include <vector> #include <algorithm> #include <unordered_map> #include <map> using namespace std; long long count_triples(vector<int> H) { int n = H.size(); long long res = 0; if (n <= 100) { for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { vector<int> h = {H[i], H[j], H[k]}; vector<int> d = {j - i, k - i, k - j}; sort(h.begin(), h.end()); sort(d.begin(), d.end()); if (h == d) res++; } } } return res; } bool small_values = true; for (int h : H) { if (h > 10) { small_values = false; break; } } if (small_values) { for (int i = 0; i < n; ++i) { for (int j = i + 1; j < min(n, i + 11); ++j) { for (int k = j + 1; k < min(n, i + 21); ++k) { vector<int> h = {H[i], H[j], H[k]}; vector<int> d = {j - i, k - i, k - j}; sort(h.begin(), h.end()); sort(d.begin(), d.end()); if (h == d) res++; } } } return res; } if (n <= 2000) { unordered_map<int, vector<int>> pos; for (int i = 0; i < n; ++i) { pos[H[i]].push_back(i); } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int d1 = j - i; for (int h3 = 1; h3 < n; ++h3) { if (pos.find(h3) == pos.end()) continue; auto& indices = pos[h3]; auto it = upper_bound(indices.begin(), indices.end(), j); for (; it != indices.end(); ++it) { int k = *it; vector<int> h = {H[i], H[j], h3}; vector<int> d = {j - i, k - i, k - j}; sort(h.begin(), h.end()); sort(d.begin(), d.end()); if (h == d) res++; } } } } return res; } bool non_decreasing = true; for (int i = 1; i < n; ++i) { if (H[i] < H[i-1]) { non_decreasing = false; break; } } if (non_decreasing) { unordered_map<int, vector<int>> pos; for (int i = 0; i < n; ++i) { pos[H[i]].push_back(i); } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int d1 = j - i; for (int h3 = 1; h3 < n; ++h3) { if (pos.find(h3) == pos.end()) continue; auto& indices = pos[h3]; auto it = upper_bound(indices.begin(), indices.end(), j); for (; it != indices.end(); ++it) { int k = *it; vector<int> h = {H[i], H[j], h3}; vector<int> d = {j - i, k - i, k - j}; sort(h.begin(), h.end()); sort(d.begin(), d.end()); if (h == d) res++; } } } } return res; } map<int, vector<int>> height_positions; for (int i = 0; i < n; i++) { height_positions[H[i]].push_back(i); } int limit = min(n, n <= 50000 ? n : 5000); for (int i = 0; i < limit; ++i) { for (int j = i + 1; j < min(n, i + limit/2); ++j) { int d1 = j - i; for (auto& [height, positions] : height_positions) { if (height > 2 * d1) break; auto it = upper_bound(positions.begin(), positions.end(), j); for (; it != positions.end() && *it < min(n, i + limit); ++it) { int k = *it; vector<int> h = {H[i], H[j], height}; vector<int> d = {j - i, k - i, k - j}; sort(h.begin(), h.end()); sort(d.begin(), d.end()); if (h == d) res++; } } } } return res; } vector<int> construct_range(int M, int K) { vector<int> result; if (M == 20 && K == 30) { result = {1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5}; } else if (M == 500 && K == 2000) { for (int cycle = 0; cycle < 25; cycle++) { for (int h = 1; h <= 20 && result.size() < M; h++) { result.push_back(h); } } } else if (M == 5000 && K == 50000) { for (int cycle = 0; cycle < 100; cycle++) { for (int h = 1; h <= 50 && result.size() < M; h++) { result.push_back(h); } } } else if (M == 30000 && K == 700000) { for (int i = 0; i < M; i++) { result.push_back((i % 100) + 1); } } else if (M == 100000 && K == 2000000) { for (int i = 0; i < M; i++) { result.push_back((i % 200) + 1); } } else if (M == 200000 && K == 12000000) { for (int i = 0; i < M; i++) { result.push_back((i % 400) + 1); } } else { for (int i = 0; i < M && i < 3; i++) { result.push_back(i + 1); } while (result.size() < M) { result.push_back(1); } } long long actual_count = count_triples(result); return result; }
#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...