Tikut

#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=0, 
        maxCutsAmount, remMinLen, remMaxLen;


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

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


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

        // jos tikku on liian pieni
        if (stickLen < bigToler) continue;


        piecesAmountMax = stickLen/bigToler; // problem jos pituus 10. tulee joko 3 tai 5 palaa ei 4

        // paljonko jää jäljelle kun jaetaan mahollisimman isoihin osiin
        remMinLen = stickLen % bigToler;

         // ??? muista käyttää

        // jos jäljelle ei jää mitään, jako menee tasan
        if (remMinLen == 0) {
            minCutsAmount = piecesAmountMax - 1;
            break;
        }

        // jos jäljelle jää liian pieni pätkä, katson jos sen voi jakaa muille osille ylittämättä rajaa
        if (bigToler + remMinLen/piecesAmountMax + bool(remMinLen%piecesAmountMax) <= maxToler) {
            minCutsAmount = piecesAmountMax - 1;
            break;
        }

        remMaxLen = remMinLen + piecesAmountMax*(bigToler - minToler);

        // jos jäljelle jää hyväksyttävän pitune pätkä
        if (remMaxLen >= minToler) {
            minCutsAmount = piecesAmountMax;
            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())),
        tempShorts;
    
    int maxDiffer = longst - shorts,
        minDiffer = maxDiffer;
        
    // int thisLoopCount = 0;
        
    bool valid = false;

    // std::cout << "\n"; 
    // for (auto i : stickLenSet) std::cout << i << " ";
    // std::cout << "\n\n"; 
    if (shorts*2 < longst)
        tempShorts = shorts;
    else
        tempShorts = longst/2 + longst%2;

    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=tempShorts; 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);
                
                // thisLoopCount++;
                
                if (valid) {
                    minDiffer = tDif;
                    // std::cout << "valid\n";
                    break;
                } 
            }
            if (valid) {
                break;
            }
 
        }
        // std::cout << " " << minDiffer << "\n";
        std::cout << minDiffer << " ";
    }
    //std::cout << "\n" << thisLoopCount << "\n";
}

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

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