Submission #1254344

#TimeUsernameProblemLanguageResultExecution timeMemory
1254344pramad712Circus (Balkan15_CIRCUS)C++20
0 / 100
56 ms1644 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)

grader.cpp: In function 'int main()':
grader.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d", &N, &M);
      |         ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d", &P[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grader.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
grader.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~
#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...