Tikut

#include <bits/stdc++.h>
// #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() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    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;
 
        // 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())),
        startDif=0;
    
    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"; 
 
    int cuts = 1, shortsTemp, longstTemp, secLongst;
 
    if (stickLenSet.size() > 1)
        secLongst = *(----stickLenSet.end());
    else
        secLongst = longst/2 + longst%2;
 
 
    if (longst > 2*shorts) 
        shortsTemp = shorts;
    else
        shortsTemp = longst/2;
 
    if (longst > secLongst*2)
        longstTemp = longst/2 + longst%2;
    else
        longstTemp = secLongst;
    
    for (; cuts<lenAmount[longst]+1; cuts++) { //händlää pisimmät
        if (cuts < lenAmount[longst]) 
            std::cout << longst - shortsTemp << " ";
        else
            std::cout << longstTemp - shortsTemp << " ";
    }
 
    std::cout << "done" << cuts << "\n";
 
    int piecesAmountMax, remMinLen, neccCuts=0;
    bool breakThis = false;
    
    for (; cuts<maxCuts+1; cuts++) {
        minDiffer = maxDiffer;
 
        // do with every cut amount k = 1, 2, 3, ..., m
        for (int tDif=startDif; tDif < longst; tDif++) {
 
            // have a target len for the shortest possible stick in the end, tShoLen
            for (int tShoLen=shortsTemp; tShoLen > 0; tShoLen--) {
                breakThis = false;
                
                // figure out if you can reach the range at all
                for (auto stickLen : stickLenSet) {
                    piecesAmountMax = stickLen/tShoLen,
                    remMinLen = stickLen % tShoLen;
 
                    if (remMinLen / piecesAmountMax + bool(remMinLen % piecesAmountMax) > tDif) {
                        neccCuts++;
                        // thisLoopCount++;
                        breakThis = true;
                        break;
                    }
                }
                if (breakThis) continue;
 
                // 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 << "\n";
        std::cout << minDiffer << " ";
    }
    // std::cout << "\n" << thisLoopCount << "\n";
}

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

Test 13

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

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