Tikut

input/code.cpp: In function 'std::vector<int> getMinMaxCuts(int, int, int, int)':
input/code.cpp:68:47: warning: unused variable 'remRemLen' [-Wunused-variable]
   68 |         minCutsAmount, maxCutsAmount, remLen, remRemLen, maxEndLen, cuts;
      |                                               ^~~~~~~~~
input/code.cpp:68:58: warning: unused variable 'maxEndLen' [-Wunused-variable]
   68 |         minCutsAmount, maxCutsAmount, remLen, remRemLen, maxEndLen, cuts;
      |                                                          ^~~~~~~~~
input/code.cpp:68:69: warning: unused variable 'cuts' [-Wunused-variable]
   68 |         minCutsAmount, maxCutsAmount, remLen, remRemLen, maxEndLen, cuts;
      |                                                                     ^~~~
input/code.cpp:110:41: warning: 'minCutsAmount' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |     return {minCutsAmount, maxCutsAmount};
      |                                         ^

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>

const int INF = 1000001;
 
std::vector<int> getMinMaxCuts(
    int tShoLen, int tDif, int stickLen, int stickAmount);

bool tryMinDiffer(
    int cuts, int tShoLen, int tDif, 
    std::unordered_map<int, int> &lenAmount, 
    std::set<int> stickLenSet);
 
void solveDotSolve(
    int maxCuts,
    std::unordered_map<int, int> &lenAmount,
    std::set<int> &stickLenSet);
 
std::unordered_map<int, int> getInput(int &maxCuts, 
    std::set<int> &stickLenSet) 
{
    /*
    changes maxCuts to the amount of cuts (m)
    inserts different stick lens to set stickLenSet, it will have all lens in sorted order
    returns lenAmount containing (len : amount) pairs
    */
    int sticksAmount, stickLen;
    std::unordered_map<int, int> lenAmount;
 
    std::cin >> sticksAmount >> maxCuts;
 
    for (int i=0; i<sticksAmount; i++) {
        std::cin >> stickLen;
        lenAmount[stickLen]++;
        stickLenSet.insert(stickLen);
    }
    
    return lenAmount;
}
 
int main() {
    int maxCuts;
    std::unordered_map<int, int> lenAmount;
    std::set<int> stickLenSet;
 
    lenAmount = getInput(maxCuts, stickLenSet);
 
    solveDotSolve(maxCuts, lenAmount, stickLenSet);
    
    
    
    return 0;
}
 
std::vector<int> getMinMaxCuts(
    int tShoLen, int toler, int stickLen, int stickAmount) 
{
    /*
    simple, get min and max cuts that can result in the stick ending up in rhe range

    ...turns out this ain't so simple...
    */
    //
    int minToler=tShoLen,
        maxToler=tShoLen + toler, 
        minCutsAmount, maxCutsAmount, remLen, remRemLen, maxEndLen, cuts;


    // find most cuts
    int piecesAmountMax = stickLen/minToler;
    remLen = stickLen % minToler;

    if (remLen / piecesAmountMax + bool(remLen % piecesAmountMax) > toler) return {INF, INF};
    
    maxCutsAmount = stickLen / minToler - 1;


    for (int bigToler=maxToler; bigToler>=minToler; bigToler--) {
        // std::cout << " " << bigToler << " last\n"; // VERY GOOD
        if (stickLen < bigToler) continue;

        piecesAmountMax = stickLen/bigToler;
        
        remLen = stickLen % bigToler;
        // remRemLen = remLen % minToler;
        if (remLen == 0) {
            minCutsAmount = piecesAmountMax - 1;
            break;
        }

        // if (remLen < minToler and minToler != bigToler) continue;
        if (remLen >= minToler) {
            minCutsAmount = piecesAmountMax;
            break;
        } 
        
        if (bigToler + remLen / piecesAmountMax + bool(remLen % piecesAmountMax) > maxToler) continue;

        minCutsAmount = piecesAmountMax - 1;

        // if (remLen/minToler + bool(remRemLen % piecesAmountMax));
        // std::cout << "\n " << tShoLen << " " << toler << " " << bigToler << "\n";
        
        break;
    }

    // std::cout << "  gMMC returns: " << minCutsAmount << " " << maxCutsAmount << " at " << tShoLen << " + " << toler << " " << stickLen << "\n"; // THE GOODEST
    return {minCutsAmount, maxCutsAmount};
}

bool tryMinDiffer(
    int cuts, int tShoLen, int tDif, 
    std::unordered_map<int, int> &lenAmount, 
    std::set<int> stickLenSet) 
{
    /*
    cuts = how many cuts I must do
    tShoLen = what the shortest stick should end up being
    tDif = the largest difference between longest and shortest stick
    lenAmount = contains (length : amount) pairs of sticks
    ***
    maxUsedCuts = maximium amount of cuts to achive the range 
    minUsedCuts = minimium amount of cuts to achive the range
    ***
    return = check if can be cut to get in range
    */
    //
    int maxUsedCuts=0, minUsedCuts=0, longstLen, longstAmount,
        maxLoops = static_cast<int>(stickLenSet.size());
 
    std::vector<int> minMaxCuts;
    
 
    // find least and most amounts of cuts to get all sticks in the acceptable range
    // if cuts not in this range, return bigger than acceptable num
    for (int i=0; i<maxLoops; i++) {
        // cut longest stick into the range each loop
        longstLen = static_cast<int>(*stickLenSet.rbegin());
        if (longstLen < 2*tShoLen) break;
        longstAmount = lenAmount[longstLen];
        
        stickLenSet.erase(--stickLenSet.end());

        // std::cout << " params gMMC: " << tShoLen << " " << tDif << " " 
        //     << longstLen << " " << longstAmount << "\n";
        minMaxCuts = getMinMaxCuts(tShoLen, tDif, longstLen, longstAmount);
        minUsedCuts += longstAmount*minMaxCuts[0];
        maxUsedCuts += longstAmount*minMaxCuts[1];
        // std::cout << " " << minUsedCuts << " " << cuts << " " << maxUsedCuts << "\n";


        if (minUsedCuts > cuts) return false;
    }
    if (stickLenSet.size() != 0)
        if (*(--stickLenSet.end())>tShoLen+tDif)
            return false;

    if (minUsedCuts <= cuts and maxUsedCuts >= cuts) return true;
    
    return false;
}
 
void solveDotSolve(
    int maxCuts,
    std::unordered_map<int, int> &lenAmount,
    std::set<int> &stickLenSet) 
{
    int longst = static_cast<int>(*(--stickLenSet.end())),
        shorts = static_cast<int>(*(stickLenSet.begin()));
    
    int maxDiffer = longst - shorts,
        minDiffer = maxDiffer;
        
    bool valid = false;

    // std::cout << "\n"; 
    // for (auto i : stickLenSet) std::cout << i << " ";
    // std::cout << "\n\n"; 
 
    for (int cuts=1; cuts<maxCuts+1; cuts++) {
        minDiffer = maxDiffer;
        // do with every cut amount k = 1, 2, 3, ..., m
        for (int tDif=0; tDif < longst; tDif++) {
            // have a target len for the shortest possible stick in the end, tShoLen
            for (int tShoLen=shorts; tShoLen > 0; tShoLen--) {
                // std::cout << tDif << " " << tShoLen << "\n";
                // have a maximium difference of the shortest (tShoLen) and longest stick in the end
                // attempt to get all sticks in range [tShoLen, tShoLen+tDif]
                
                // std::cout << "params: " << cuts << " " << tShoLen << " " << tDif << "\n";
                valid = tryMinDiffer(cuts, tShoLen, tDif, lenAmount, stickLenSet);
                
                if (valid) {
                    minDiffer = tDif;
                    // std::cout << "valid\n";
                    break;
                } 
            }
            if (valid) {
                break;
            }
 
        }
        std::cout << minDiffer << " ";
    }
}

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 5

Group: 2, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 5, 6

Verdict: ACCEPTED

Test 7

Group: 3, 5, 6

Verdict: ACCEPTED

Test 8

Group: 3, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 5, 6

Verdict: ACCEPTED

Test 12

Group: 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED