Tikut

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

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 tDif, int stickLen, int stickAmount) 
{
    /*
    simple, get min and max cuts that can result in the stick ending up in rhe range
    */
    // can't be divided into pieces wihing range [tShoLen, tShoLen+tDif] if true
    if (tShoLen + stickLen%tShoLen > tShoLen + tDif) return {1000001, 1000001};
    
    int maxCutsAmount = stickLen / tShoLen - 1;
    
    int minCutsAmount = maxCutsAmount;

    for (int cutsAmount=0; cutsAmount<=maxCutsAmount; cutsAmount++) {
        if (stickLen/(cutsAmount+1) + bool(stickLen%(cutsAmount+1)) <= tShoLen + tDif) {
            minCutsAmount = cutsAmount;
            // std::cout << "found " << stickLen << " : " << minCutsAmount << " " << maxCutsAmount << "\n";
            break;
        }
    }

    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 = smallest difference between the longest stick and shortest stick
    */
    //
    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());
        
        minMaxCuts = getMinMaxCuts(tShoLen, tDif, longstLen, longstAmount);
        minUsedCuts += longstAmount*minMaxCuts[0];
        maxUsedCuts += longstAmount*minMaxCuts[1];
        //std::cout << cuts << " " << minUsedCuts << " " << maxUsedCuts << "\n";

        if (minUsedCuts > cuts) 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;

    for (int cuts=1; cuts<maxCuts+1; cuts++) {
        minDiffer = maxDiffer;
        // do with every cut amount k = 1, 2, 3, ..., m
        for (int tShoLen=shorts; tShoLen > 0; tShoLen--) {
            // have a target len for the shortest possible stick in the end, tShoLen
            for (int tDif=0; tDif < minDiffer; tDif++) {
                // 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 << "\n" << cuts << " " << tShoLen << " " << tDif << "\n" 
                //     << lenAmount[1] << " " << lenAmount[2] << " " << lenAmount[3] << " "
                //     << lenAmount[4] << " " << lenAmount[5] << "\n";
                // for (auto i : stickLenSet) std::cout << i << " ";
                // std::cout << "\n"; 
                
                valid = tryMinDiffer(cuts, tShoLen, tDif, lenAmount, stickLenSet);

                if (valid) {
                    minDiffer = tDif;
                    // std::cout << "\nvalid\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: WRONG ANSWER

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: WRONG ANSWER

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: 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: 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