# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1254344 | pramad712 | Circus (Balkan15_CIRCUS) | C++20 | 56 ms | 1644 KiB |
#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> positions;
vector<int> minimals;
int binary_search(int placement) {
int minimal = 0, maximal = 1000000000;
while (minimal < maximal) {
int middle = minimal + (maximal - minimal) / 2; // Prevent overflow
int end = placement + middle;
// Find the rightmost position <= end
int index = upper_bound(positions.begin(), positions.end(), end) - positions.begin() - 1;
// Bounds check
if (index < 0 || index >= positions.size()) {
minimal = middle + 1;
continue;
}
int height = positions[index] - placement;
// Check if this height is sufficient
if (height >= 0 && height >= minimals[index]) {
maximal = middle;
} else {
minimal = middle + 1;
}
}
return minimal;
}
void init(int N, int M, int P[]) {
positions.clear();
minimals.clear();
// Sort positions in descending order
sort(P, P + N, greater<int>());
// Add boundary position M
positions.push_back(M);
minimals.push_back(0);
// Add all pole positions and calculate minimum heights needed
for (int i = 0; i < N; i++) {
int position = P[i];
int min_height = binary_search(position);
minimals.push_back(min_height);
positions.push_back(position);
}
// Add boundary position 0
int min_height_0 = binary_search(0);
minimals.push_back(min_height_0);
positions.push_back(0);
// Reverse to get ascending order
reverse(minimals.begin(), minimals.end());
reverse(positions.begin(), positions.end());
}
int minLength(int placement) {
return binary_search(placement);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |