Submission #1254344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254344		pramad712	Circus (Balkan15_CIRCUS)	C++20	0 / 100	56 ms	1644 KiB

circus

#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);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9