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 (stickLen%tShoLen > tDif) return {1000001, 1000001};
    
    int maxCutsAmount = stickLen / tShoLen - 1;
    
    int minCutsAmount = maxCutsAmount;
 
    int minShoLen;
 
    for (int maxShoLen=tShoLen+tDif; maxShoLen >= tShoLen; maxShoLen--) {
        minShoLen = stickLen % maxShoLen;
        // std::cout << "  minMaxShoLens: " << minShoLen << " " << maxShoLen <<"\n";
        if (minShoLen >= tShoLen) {
            minCutsAmount = stickLen / maxShoLen;
            // std::cout << "  found " << stickLen << " : " << minCutsAmount << " "
            //     << maxCutsAmount << "\n";
            break;
        } else if (minShoLen == 0) {
            minCutsAmount = stickLen / maxShoLen - 1;
            // 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 = 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 tShoLen=shorts; tShoLen > 0; tShoLen--) {
            // have a target len for the shortest possible stick in the end, tShoLen
            for (int tDif=0; tDif < longst; 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 << "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: ACCEPTED

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