CSES - Datatähti 2025 alku - Results
Submission details
Task:Tikut
Sender:Chenran
Submission time:2024-11-10 20:47:38 +0200
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:60:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   60 |     sort(A, A + n, greater<int>());
      |     ^~~~
      |     short

Code

#include <iostream>
#include <queue>

using namespace std;

int ceil(int a, int b)
{
    return (a + b - 1) / b;
}

struct Stick
{
    int length;
    int max_length;
    int min_length;
    int cut_count;
    int next_cut_max;
    int next_cut_min;

    bool operator>(const Stick &other) const
    {
        if (max_length != other.max_length)
            return max_length > other.max_length;
        return next_cut_min > other.next_cut_min;
    }

    bool operator<(const Stick &other) const
    {
        if (max_length != other.max_length)
            return max_length < other.max_length;
        return next_cut_min < other.next_cut_min;
    }

    bool operator==(const Stick &other) const
    {
        return max_length == other.max_length &&
               next_cut_min == other.next_cut_min;
    }

    void cut()
    {
        cut_count++;
        max_length = next_cut_max;
        min_length = next_cut_min;
        next_cut_max = ceil(length, cut_count + 2);
        next_cut_min = length / (cut_count + 2);
    }
};

int main()
{
    int n, m;
    cin >> n >> m;

    int A[n];
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    sort(A, A + n, greater<int>());

    Stick sticks[n];
    for (int i = 0; i < n; i++)
    {
        sticks[i].length = A[i];
        sticks[i].max_length = A[i];
        sticks[i].min_length = A[i];
        sticks[i].cut_count = 0;
        sticks[i].next_cut_max = ceil(A[i], 2);
        sticks[i].next_cut_min = A[i] / 2;
    }

    priority_queue<Stick> sticks_queue;
    for (int i = 0; i < n; i++)
    {
        sticks_queue.push(sticks[i]);
    }

    int min_length = sticks[n - 1].length;
    while (m--)
    {
        Stick stick = sticks_queue.top();
        sticks_queue.pop();

        stick.cut();
        sticks_queue.push(stick);

        int max_length = sticks_queue.top().max_length;
        min_length = min(min_length, stick.min_length);
        int max_length_diff = max_length - min_length;

        cout << max_length_diff << " ";
    }
    cout << endl;

    return 0;
}