CSES - Datatähti 2025 alku - Results
Submission details
Task:Tikut
Sender:OnniHak
Submission time:2024-11-10 17:45:57 +0200
Language:C++ (C++17)
Status:READY
Result:15
Feedback
groupverdictscore
#1ACCEPTED7
#2ACCEPTED8
#30
#40
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 4, 5, 6details
#3ACCEPTED0.00 s1, 4, 5, 6details
#4ACCEPTED0.00 s1, 4, 5, 6details
#5ACCEPTED0.00 s2, 5, 6details
#6ACCEPTED0.01 s2, 5, 6details
#7ACCEPTED0.26 s3, 5, 6details
#8--3, 5, 6details
#9--3, 5, 6details
#10ACCEPTED0.14 s3, 5, 6details
#11ACCEPTED0.01 s3, 5, 6details
#12ACCEPTED0.16 s4, 5, 6details
#13--4, 5, 6details
#14ACCEPTED0.57 s4, 5, 6details
#15--4, 5, 6details
#16--5, 6details
#17--5, 6details
#18--5, 6details
#19--5, 6details
#20--6details
#21--6details
#22--6details

Compiler report

input/code.cpp: In function 'void solveDotSolve(int, std::unordered_map<int, int>&, std::set<int>&)':
input/code.cpp:196:31: warning: unused variable 'longstTemp' [-Wunused-variable]
  196 |     int cuts = 1, shortsTemp, longstTemp, secLongst = *(----stickLenSet.end());
      |                               ^~~~~~~~~~
input/code.cpp:196:43: warning: unused variable 'secLongst' [-Wunused-variable]
  196 |     int cuts = 1, shortsTemp, longstTemp, secLongst = *(----stickLenSet.end());
      |                                           ^~~~~~~~~

Code

#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 = *(----stickLenSet.end());


    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 << "\n" << shortsTemp << "\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 details

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

input
1 1
6

correct output

user output

Test 2

Group: 1, 4, 5, 6

Verdict: ACCEPTED

input
5 10
4 8 6 2 7

correct output
5 4 2 2 2 1 1 1 1 1 

user output
5 4 2 2 2 1 1 1 1 1 

Test 3

Group: 1, 4, 5, 6

Verdict: ACCEPTED

input
5 10
5 5 8 6 7

correct output
3 3 2 3 2 2 1 1 1 2 

user output
3 3 2 3 2 2 1 1 1 2 

Test 4

Group: 1, 4, 5, 6

Verdict: ACCEPTED

input
5 10
8 7 9 6 10

correct output
4 4 3 3 2 2 1 2 2 1 

user output
4 4 3 3 2 2 1 2 2 1 

Test 5

Group: 2, 5, 6

Verdict: ACCEPTED

input
1000 1071
3 2 3 1 3 3 2 3 2 3 2 2 2 1 2 ...

correct output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

user output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

Test 6

Group: 2, 5, 6

Verdict: ACCEPTED

input
1000 1500
3 2 2 3 2 3 2 2 2 3 2 2 3 3 3 ...

correct output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

user output
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

Test 7

Group: 3, 5, 6

Verdict: ACCEPTED

input
1000 2
15 710 210 347 398 66 318 277 ...

correct output
994 994 

user output
994 994 

Test 8

Group: 3, 5, 6

Verdict:

input
1000 2
743 890 592 942 736 969 616 50...

correct output
498 496 

user output
(empty)

Test 9

Group: 3, 5, 6

Verdict:

input
1000 2
987 968 920 994 988 918 914 95...

correct output
500 500 

user output
(empty)

Test 10

Group: 3, 5, 6

Verdict: ACCEPTED

input
1000 2
996 1000 998 998 999 997 997 9...

correct output
500 500 

user output
500 500 

Test 11

Group: 3, 5, 6

Verdict: ACCEPTED

input
1000 2
501 501 501 501 501 501 501 50...

correct output
1 168 

user output
1 168 

Test 12

Group: 4, 5, 6

Verdict: ACCEPTED

input
100 200
145 136 74 83 73 36 196 115 11...

correct output
194 190 189 183 182 181 181 17...

user output
194 190 189 183 182 181 181 17...

Test 13

Group: 4, 5, 6

Verdict:

input
100 200
157 110 168 155 192 107 146 15...

correct output
95 96 96 95 93 94 94 94 90 91 ...

user output
(empty)

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

input
50 200
137 118 160 118 146 160 140 18...

correct output
98 98 98 96 90 91 88 88 84 86 ...

user output
98 98 98 96 90 91 88 88 84 86 ...

Test 15

Group: 4, 5, 6

Verdict:

input
100 200
147 174 186 148 155 128 158 18...

correct output
99 99 98 98 97 97 96 96 95 95 ...

user output
(empty)

Test 16

Group: 5, 6

Verdict:

input
1000 2000
928772177 816188227 216592201 ...

correct output
991676844 990940224 990685481 ...

user output
(empty)

Test 17

Group: 5, 6

Verdict:

input
1000 2000
665759876 597950008 615453266 ...

correct output
498801198 498681904 498504321 ...

user output
(empty)

Test 18

Group: 5, 6

Verdict:

input
500 2000
683288817 784230412 626685186 ...

correct output
497667621 498434895 495465990 ...

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
1000 2000
666667000 809309500 571572000 ...

correct output
499499500 499249250 498999000 ...

user output
(empty)

Test 20

Group: 6

Verdict:

input
100000 200000
861772559 734298084 983382252 ...

correct output
499973914 499985299 499985141 ...

user output
(empty)

Test 21

Group: 6

Verdict:

input
30000 200000
691834579 617419813 514778075 ...

correct output
499967533 499976270 499969810 ...

user output
(empty)

Test 22

Group: 6

Verdict:

input
100000 200000
820255000 960780000 741965000 ...

correct output
499995000 499992500 499990000 ...

user output
(empty)