Tikut

input/code.cpp: In function 'void bruteForce(std::vector<int>, int, int&, int&)':
input/code.cpp:81:48: error: wrong number of template arguments (0, should be 1)
   81 |     sort(sticks.begin(), sticks.end(), greater<>());
      |                                                ^
In file included from /usr/include/c++/11/string:48,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from input/code.cpp:1:
/usr/include/c++/11/bits/stl_function.h:385:12: note: provided for 'template<class _Tp> struct std::greater'
  385 |     struct greater : public binary_...

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
struct Frac
{
    int number;
    int divisor;
    double result;
 
    void update()
    {
        result = (double)number / (double)divisor;
    }
 
    Frac(int _number, int _divisor)
    {
        number = _number;
        divisor = _divisor;
        update();
    }
 
    bool operator<(Frac frac) const
    {
        return result < frac.result;
    }
};
 
multiset<Frac> numbersSorted;
 
void printSet()
{
    cout << "printing set:\n";
    for (Frac frac : numbersSorted) {
        cout << frac.number << " " << frac.divisor << " " << frac.result << "\n";
    }
}
 
void printDifference()
{
    Frac fracSmall = *numbersSorted.begin();
    int smallestNumber = fracSmall.number / fracSmall.divisor;
 
    Frac fracBig = *numbersSorted.rbegin();
    int biggestNumber = fracBig.number / fracBig.divisor;
    if (fracBig.number % fracBig.divisor != 0) {
        biggestNumber += 1;
    }
    cout << (biggestNumber - smallestNumber);
}

int getMax(int number, int div)
{
    int ans = number / div;
    if (number % div != 0) {
        ans += 1;
    }
    return ans;
}
 
int getMin(int number, int div)
{
    int ans = number / div;
    return ans;
}

void bruteForce(vector<int> sticks, int m, int& ans1, int& ans2)
{
    if (sticks.size() == 1) {
        if (m >= 1) {
            int difference = getMax(sticks[0], 2) - getMin(sticks[0], 2);
            ans1 = difference;
        }
        if (m == 2) {
            int difference = getMax(sticks[0], 3) - getMin(sticks[0], 3);
            ans2 = difference;
        }
        return;
    }
    sort(sticks.begin(), sticks.end(), greater<>());
 
    if (m >= 1) {
        int difference = max(getMax(sticks[0], 2), sticks[1]) - min(getMin(sticks[0], 2), sticks.back());
        ans1 = difference;
    }
    if (m == 2) {
        int maxLenDiv2 = max(getMax(sticks[0], 2), getMax(sticks[1], 2));
        if (sticks.size() >= 3) {
            maxLenDiv2 = max(maxLenDiv2, sticks[2]);
        }
        int minLenDiv2 = min(getMin(sticks[0], 2), getMin(sticks[1], 2));
        if (sticks.size() >= 3) {
            minLenDiv2 = min(minLenDiv2, sticks.back());
        }
        int div2Difference = maxLenDiv2 - minLenDiv2;
        
        int maxLenDiv3 = max(getMax(sticks[0], 3), sticks[1]);
        int minLenDiv3 = min(getMin(sticks[0], 3), sticks.back());
        int div3Difference = maxLenDiv3 - minLenDiv3;
        int ans = min(div2Difference, div3Difference);
        ans2 = ans;
    }
}
 
void runBruteForce(int n, int m)
{
    vector<int> sticks;
    
    for (int i = 0; i < n; i++) {
        int number;
        cin >> number;
        sticks.push_back(number);
    }
    int ans1, ans2;
    bruteForce(sticks, m, ans1, ans2);
    cout << ans1;
    if (m == 2) {
        cout << " " << ans2;
    }
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    if (m <= 2) {
        runBruteForce(n, m);
        return 0;
    }
    //n = 3; m = 4; vector<int> testNumbers = {3, 4, 5};
    //n = 2; m = 6; vector<int> testNumbers = {2, 6};
 
    for (int i = 0; i < n; i++) {
        int number;
        cin >> number;
        //number = testNumbers[i];
        numbersSorted.emplace(number, 1);
    }
 
    for (int k = 0; k < m; k++) {
        //printSet();
 
        Frac frac = *numbersSorted.rbegin();
        Frac newFrac = Frac(frac.number, frac.divisor + 1);
        
        numbersSorted.erase(--numbersSorted.end());
        //cout << "size = " << numbersSorted.size() << "\n";
        numbersSorted.insert(newFrac);
        //cout << "size = " << numbersSorted.size() << "\n";
 
        printDifference();
        //cout << "\n";
        if (k != m - 1) {
            cout << " ";
        }
    }
    //printSet();
}