Tikut

input/code.cpp: In member function 'bool Frac::operator<(Frac) const':
input/code.cpp:31:13: warning: unused variable 'decreaseMax' [-Wunused-variable]
   31 |         int decreaseMax = 0;
      |             ^~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:282:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  282 |                     for (int i = 0; i < testNumbers.size(); i++) {
      |                                     ~~^~~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int minNumber = INT_MAX;
int maxNumber = -1;
int secondMaxNumber = -1;
 
struct Frac
{
    int number;
    int divisor;
    int resultMax;
    int resultMinDivPlusOne;
 
    Frac(int _number, int _divisor)
    {
        number = _number;
        divisor = _divisor;
        
        resultMinDivPlusOne = max(number / (divisor + 1), 1);
        resultMax = _number / _divisor;
        if (_number % _divisor != 0) {
            resultMax += 1;
        }
    }
 
    bool operator<(Frac frac) const
    {
        int decreaseMax = 0;
        if (maxNumber == secondMaxNumber) {
            
        }
        int thisAns = min(maxNumber - resultMax, 0) - max(minNumber - resultMinDivPlusOne, 0);
 
        int otherAns = frac.resultMax - max(minNumber - frac.resultMinDivPlusOne, 0);
 
        //if (thisAns == otherAns) {
            //cout << "first = " << (number / (divisor + 1)) << "\n";
            //cout << "second = " << (frac.number / (frac.divisor + 1)) << "\n";
 
        //    return (number / (divisor + 1)) < (frac.number / (frac.divisor + 1));
        //}
        return thisAns < otherAns;
    }
};
 
multiset<Frac> numbersSorted;
multiset<int> biggestNumbers;
 
void printSet()
{
    cout << "\n";
    cout << "printing set:\n";
    for (Frac frac : numbersSorted) {
        cout << frac.number << " " << frac.divisor << " " << frac.resultMax << "    ";
    }
    cout << "\n";
    cout << "printing biggestNumbers:\n";
    for (int number : biggestNumbers) {
        cout << number << " ";
    }
    cout << "\n\n";
}
 
int getWorkingDifference()
{
    return maxNumber - minNumber;
}
 
void shuffle(int& n, int& m, vector<int>& testNumbers)
{
    minNumber = INT_MAX;
    n = (rand() % 10) + 1;
    
    int sum = 0;
    numbersSorted.clear();
    testNumbers.clear();
    biggestNumbers.clear();
    for (int i = 0; i < n; i++) {
        int random = (rand() % 1000) + 1;
        testNumbers.push_back(random);
        sum += random;
    }
    sum -= n;
    m = min((rand() % 2) + 1, sum);
}
 
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, m;
    cin >> n >> 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()
{
    /*Frac frac1(14, 7);
    Frac frac2(13, 9);
    cout << (frac1 < frac2) << " " << (frac2 < frac1);
    return 0;*/
    /*cout << "start";
    for (int x = 0; x < 100; x++) {
        for (int y = 0; y < 100; y++) {
            for (int xd = 1; xd < 100; xd++) {
                for (int yd = 1; yd < 100; yd++) {
                    if (x == y) {
                        continue;
                    }
                    Frac fracX(x, xd);
                    Frac fracY(y, yd);
                    if ((fracX < fracY) == (fracY < fracX)) {
                        //cout << "yes = " << x << " " << y << " " << xd << " " << yd << "\n";
 
                        Frac fracX1(x, xd + 1);
                        Frac fracY1(y, yd + 1);
 
                        int minX = fracX.number / fracX.divisor;
                        int minY = fracY.number / fracY.divisor;
                        int minX1 = fracX1.number / fracX1.divisor;
                        int minY1 = fracY1.number / fracY1.divisor;
 
                        int maxX = minX;
                        if (fracX.number % fracX.divisor != 0) {
                            maxX += 1;
                        }
                        int maxY = minY;
                        if (fracY.number % fracY.divisor != 0) {
                            maxY += 1;
                        }
                        int maxX1 = minX1;
                        if (fracX1.number % fracX1.divisor != 0) {
                            maxX1 += 1;
                        }
                        int maxY1 = minY1;
                        if (fracY1.number % fracY1.divisor != 0) {
                            maxY1 += 1;
                        }
 
                        if (!(min(minX, minY1) == min(minY, minX1))) {
                            cout << "WHAT\n";
                            cout << x << " " << y << " " << xd << " " << yd << "\n";
                            cout << minX << " " << minY << " " << minX1 << " " << minY1 << "\n";
                        }
                    }
                }
            }
        }
    }
    cout << "end";
    return 0;*/
    int n, m;
    //cin >> n >> m;
    //n = 3; m = 9; vector<int> testNumbers = {3, 4, 5};
    //n = 2; m = 6; vector<int> testNumbers = {2, 6};
    //m = 9; vector<int> testNumbers = {1000, 999, 999, 500, 500, 100}; n = testNumbers.size();
    //m = 10; vector<int> testNumbers = {3, 5, 5, 9, 9}; n = testNumbers.size();
    //m = 10; vector<int> testNumbers = {10, 11}; n = testNumbers.size();
    //m = 2; vector<int> testNumbers = {577, 291}; n = testNumbers.size();
    //m = 2; vector<int> testNumbers = {523, 455, 399, 565, 366, 64, 284, 983, 294, 288, 223, 35, 192, 382, 360, 884, 239, 636, 940, 679, 499}; n = testNumbers.size();
    //m = 2; vector<int> testNumbers = {876, 570, 305, 991, 844, 558, 858, 320, 876}; n = testNumbers.size();
    m = 2; vector<int> testNumbers = {536, 538, 318, 409, 825}; n = testNumbers.size();
    
 
    //for (int test = 0; test < 3000; test++) {
        //shuffle(n, m, testNumbers);
 
        //vector<int> resultsWorking;
        //runWorkingProgram(n, m, testNumbers, resultsWorking);
        int ans1 = -1, ans2 = -1;
        bruteForce(testNumbers, m, ans1, ans2);
        cout << "brute force ans = " << ans1 << " ";
        if (m == 2) {
            cout << ans2 << " ";
        }
 
        for (int i = 0; i < n; i++) {
            int number;
            //cin >> number;
            number = testNumbers[i];
            minNumber = min(minNumber, number);
            numbersSorted.emplace(number, 1);
            biggestNumbers.insert(number);
        }
        //cout << "min number = " << minNumber << "\n";
 
        for (int k = 0; k < m; k++) {
            //cout << "k=" << k << "\n";
            //if (test == 1)
                printSet();
 
            Frac oldFrac = *numbersSorted.rbegin();
            Frac newFrac = Frac(oldFrac.number, oldFrac.divisor + 1);
            
            numbersSorted.erase(--numbersSorted.end());
            biggestNumbers.extract(oldFrac.resultMax);
            numbersSorted.insert(newFrac);
 
            biggestNumbers.insert(newFrac.resultMax);
            maxNumber = *biggestNumbers.rbegin();
            secondMaxNumber = *++biggestNumbers.rbegin();
 
            minNumber = min(minNumber, newFrac.number / newFrac.divisor);
 
            int ans = getWorkingDifference();
            cout << "algo ans = " << ans << " ";
            
            if (k == 0) {
                if (ans != ans1) {
                    cout << "WHAT\n";
                }
            }
            if (k == 1) {
                if (ans != ans2) {
                    cout << "WHAT2\n";
                    for (int i = 0; i < testNumbers.size(); i++) {
                        cout << testNumbers[i] << " ";
                    }
                    cout << "\n";
                    cout << "n = " << n << " m = " << m << "\n";
                }
            }
            /*cout << ans;
            if (k != m - 1) {
                cout << " ";
            }*/
        }
        //printSet();
        //cout << "\n";
        //if (test == 1)
            printSet();
 
    //}
    cout << "end";
}

Test 1

Group: 1, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 2

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 3

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 4

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 5

Group: 2, 5, 6

Verdict: WRONG ANSWER

Test 6

Group: 2, 5, 6

Verdict: WRONG ANSWER

Test 7

Group: 3, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 3, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 3, 5, 6

Verdict: WRONG ANSWER

Test 10

Group: 3, 5, 6

Verdict: WRONG ANSWER

Test 11

Group: 3, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 6

Verdict: WRONG ANSWER

Test 21

Group: 6

Verdict: WRONG ANSWER

Test 22

Group: 6

Verdict: WRONG ANSWER