Tikut

input/code.cpp: In function 'int main()':
input/code.cpp:250:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  250 |                     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 resultMaxDivPlusOne;
    int resultMinDivPlusOne;
 
    Frac(int _number, int _divisor)
    {
        number = _number;
        divisor = _divisor;
        
        resultMinDivPlusOne = max(number / (divisor + 1), 1);
        resultMaxDivPlusOne = _number / (_divisor + 1);
        if (_number % (_divisor + 1) != 0) {
            resultMaxDivPlusOne += 1;
        }
    }

    int calculateMax()
    {
        int ans = number / divisor;
        if (number % divisor != 0) {
            ans += 1;
        }
        return ans;
    }
 
    bool operator<(Frac frac) const
    {
        // Pienin arvo pystyy aina muuttumaan pienemmänksi.
        int differenceThis = min(resultMinDivPlusOne - minNumber, 0);
        int differenceOther = min(frac.resultMinDivPlusOne - minNumber, 0);

        if (maxNumber == secondMaxNumber) {

        }
        else {
            // Suurin arvo pystyy vain muuttumaan pienemmänksi, jos on vain yksi suurin arvo.
            // Vaaditaan myös, että arvo jota pienennetään on suurin arvo.
            if (number == maxNumber) {
                differenceThis += maxNumber - max(maxNumber - resultMaxDivPlusOne, secondMaxNumber);
            }
            if (frac.number == maxNumber) {
                differenceOther += maxNumber - max(maxNumber - frac.resultMaxDivPlusOne, secondMaxNumber);
            }
        }
        //cout << "difference this = " << differenceThis << " difference other = " << differenceOther << "\n";

        if (differenceThis == differenceOther) {
            // incomplete
            return number < frac.number;
        }
        return differenceThis < differenceOther;
    }
};
 
multiset<Frac> numbersSorted;
multiset<int> biggestNumbers;
 
void printSet()
{
    cout << "\n";
    cout << "printing set:\n";
    for (Frac frac : numbersSorted) {
        cout << frac.number << " " << frac.divisor << " " << frac.resultMaxDivPlusOne << "    ";
    }
    cout << "\n";
    cout << "printing biggestNumbers:\n";
    for (int number : biggestNumbers) {
        cout << number << " ";
    }
    cout << "\n\n";
}

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(963, 2);
    Frac frac2(962, 1);
    minNumber = min(frac1.number / frac1.divisor, frac2.number / frac2.divisor);
    maxNumber = 577 / 2 + 1;
    secondMaxNumber = minNumber;
    cout << "min number = " << minNumber << " max number = " << maxNumber << " second max number = " << secondMaxNumber << "\n";
    cout << (frac1 < frac2) << "\n";
    cout << (frac2 < frac1);
    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();
    m = 2; vector<int> testNumbers = {725, 479, 359, 963, 465, 706, 146, 282, 828, 962}; n = testNumbers.size();
 
    //for (int test = 0; test < 10; test++) {
        //shuffle(n, m, testNumbers);
 
        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;
            number = testNumbers[i];
            minNumber = min(minNumber, number);
            numbersSorted.emplace(number, 1);
            biggestNumbers.insert(number);
        }
 
        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());
            numbersSorted.insert(newFrac);
 
            biggestNumbers.extract(oldFrac.calculateMax());
            biggestNumbers.insert(newFrac.calculateMax());

            maxNumber = *biggestNumbers.rbegin();
            secondMaxNumber = *++biggestNumbers.rbegin();
            cout << "max = " << maxNumber << " second max = " << secondMaxNumber << "\n";
 
            minNumber = min(minNumber, newFrac.number / newFrac.divisor);
 
            int ans = maxNumber - minNumber;
            cout << "algo ans = " << ans << " ";
            
            if (k == 0) {
                if (ans != ans1) {
                    cout << "WHAT1\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