CSES - Datatähti 2025 alku - Results
Submission details
Task:Tikut
Sender:rottis
Submission time:2024-11-02 21:56:44 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 3, 4, 5, 6details
#20.00 s1, 4, 5, 6details
#30.00 s1, 4, 5, 6details
#40.00 s1, 4, 5, 6details
#50.00 s2, 5, 6details
#60.00 s2, 5, 6details
#70.00 s3, 5, 6details
#80.00 s3, 5, 6details
#90.00 s3, 5, 6details
#100.00 s3, 5, 6details
#110.00 s3, 5, 6details
#120.00 s4, 5, 6details
#130.00 s4, 5, 6details
#140.00 s4, 5, 6details
#150.00 s4, 5, 6details
#160.00 s5, 6details
#170.00 s5, 6details
#180.00 s5, 6details
#190.00 s5, 6details
#200.08 s6details
#210.04 s6details
#220.08 s6details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:174:23: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
  174 |     for (int i = 0; i < n; i++) {
      |                     ~~^~~

Code

#include <iostream>
#include <stdlib.h>
#include <algorithm>    // std::sort

unsigned int n, m;

unsigned int *stick_lengths;


void p1_sol() {
    /* Osatehtävä 1 (7 pistettä)

        1 <= n <= 5
        1 <= m <= 10
        1 <= a_i <= 10 */
    // brute force? numbers are really small
    for (unsigned int k = 1; k <= m; k++) {
        
    }
}

// WORKS
void p2_sol() {
    /* Osatehtävä 2 (8 pistettä)

        1 <= n <= 1000
        1 <= m <= 2000
        1 <= a_i <= 3  */
    unsigned int one_count = 0;
    unsigned int two_count = 0;
    unsigned int three_count = 0;

    unsigned int *solutions = (unsigned int*) malloc(m * sizeof(unsigned int));

    for (unsigned int i = 0; i < n; i++ ) {
        switch (stick_lengths[i]) {
            case 1:
                one_count++;
                break;
            case 2:
                two_count++;
                break;
            case 3:
                three_count++;
                break;
        }
    }

    unsigned int cuts_left = m;
    unsigned int i = 0;
    while (three_count > 0 && cuts_left > 0) {
        three_count--;
        one_count++;
        two_count++;
        if (three_count > 0) {
            solutions[i] = 2;
        } else {
            solutions[i] = 1;
        }
        cuts_left--;
        i++;
    }
    while (two_count > 0 && cuts_left > 0) {
        two_count--;
        one_count += 2;
        if (two_count > 0) {
            solutions[i] = 1;
        } else {
            solutions[i] = 0;
        }
        cuts_left--;
        i++;
    }

    std::cout << solutions[0];
    for (unsigned int j = 1; j < m; j++) {
        std::cout << ' ' << solutions[j];
    }
}

void p3_sol() {
    /* Osatehtävä 3 (12 pistettä)

        1 <= n <= 1000
        1 <= m <= 2
        1 <= a_i <= 1000 */
    { // k=1
        
        unsigned int max_len = stick_lengths[n-1];
        unsigned int new_len1 = max_len >> 1;
        unsigned int new_len2 = max_len - new_len1;
        stick_lengths[n-1] = new_len1;
        stick_lengths[n] = new_len2;
        unsigned int maximum = std::max(std::max(stick_lengths[n-1], stick_lengths[n]), stick_lengths[n-2]);
        unsigned int minimum = std::min(std::min(stick_lengths[n-1], stick_lengths[n]), stick_lengths[0]);
        
        stick_lengths[n-1] = max_len;
        stick_lengths[n] = -1;
        std::cout << maximum - minimum;
    }
    
    if (m == 2) {
        // k=2
        unsigned int case_1_answer, case_2_answer;

        { // case 1: last is divided into 3 equal parts
            unsigned int max_len = stick_lengths[n-1];
            unsigned int max_len_remainder = max_len % 3;
            unsigned int new_len1 = max_len / 3;
            unsigned int new_len2 = new_len1;
            unsigned int new_len3 = new_len1;
            if (max_len_remainder == 2) {
                new_len3++;
                new_len2++;
            } else if (max_len_remainder == 1) {
                new_len3++;
            } // else div equal!

            unsigned int maximum = std::max(
                std::max(
                    std::max(stick_lengths[n-2], new_len1
                    ), new_len2
                ), new_len3
            );
            unsigned int minimum = std::min(
                std::min(
                    std::min(stick_lengths[0], new_len1
                    ), new_len2
                ), new_len3
            );
            case_1_answer = maximum - minimum;
        }

        { // case 2: last is divided into 2 equal parts, second to last is divided into 2 equal parts
            unsigned int max_len = stick_lengths[n-1];
            unsigned int new_len1 = max_len>>1;
            unsigned int new_len2 = max_len - new_len1;

            unsigned int second_max_len = stick_lengths[n-2];
            unsigned int new_len3 = second_max_len>>1;
            unsigned int new_len4 = second_max_len - new_len3;

            unsigned int maximum = std::max(
                std::max(
                    std::max(
                        std::max(
                            stick_lengths[n-2], new_len1
                        ), new_len2
                    ), new_len3
                ), new_len4
            );
            unsigned int minimum = std::min(
                std::min(
                    std::min(
                        std::min(
                            stick_lengths[0], new_len1
                        ), new_len2
                    ), new_len3
                ), new_len4
            );
            case_2_answer = maximum - minimum;
        }
        
        std::cout << ' ' << std::min(case_1_answer, case_2_answer);
    }
}

int main() {
    std::cin >> n >> m;
    stick_lengths = (unsigned int*) malloc((n + m) *sizeof(unsigned int));
    for (unsigned int i = 0; i < n; i++) {
        std::cin >> stick_lengths[i];
    }
    for (int i = 0; i < n; i++) {
        std::cout << stick_lengths[i] << ' ';
    }
    
    if (m <= 2) {
        std::sort(stick_lengths, &stick_lengths[n]);
        p3_sol();
    } else if (n <= 5) {
        p1_sol();
    } else {
        // p4, p5, p6 don't get points anyway :)
        p2_sol();
    }
    std::cout << std::endl;

    return 0;
}

Test details

Test 1

Group: 1, 3, 4, 5, 6

Verdict:

input
1 1
6

correct output

user output
(empty)

Test 2

Group: 1, 4, 5, 6

Verdict:

input
5 10
4 8 6 2 7

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

user output
4 8 6 2 7 

Test 3

Group: 1, 4, 5, 6

Verdict:

input
5 10
5 5 8 6 7

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

user output
5 5 8 6 7 

Test 4

Group: 1, 4, 5, 6

Verdict:

input
5 10
8 7 9 6 10

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

user output
8 7 9 6 10 

Test 5

Group: 2, 5, 6

Verdict:

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
3 2 3 1 3 3 2 3 2 3 2 2 2 1 2 ...

Test 6

Group: 2, 5, 6

Verdict:

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
3 2 2 3 2 3 2 2 2 3 2 2 3 3 3 ...

Test 7

Group: 3, 5, 6

Verdict:

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

correct output
994 994 

user output
15 710 210 347 398 66 318 277 ...

Test 8

Group: 3, 5, 6

Verdict:

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

correct output
498 496 

user output
743 890 592 942 736 969 616 50...

Test 9

Group: 3, 5, 6

Verdict:

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

correct output
500 500 

user output
987 968 920 994 988 918 914 95...

Test 10

Group: 3, 5, 6

Verdict:

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

correct output
500 500 

user output
996 1000 998 998 999 997 997 9...

Test 11

Group: 3, 5, 6

Verdict:

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

correct output
1 168 

user output
501 501 501 501 501 501 501 50...

Test 12

Group: 4, 5, 6

Verdict:

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

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

user output
145 136 74 83 73 36 196 115 11...

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
157 110 168 155 192 107 146 15...

Test 14

Group: 4, 5, 6

Verdict:

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
137 118 160 118 146 160 140 18...

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
147 174 186 148 155 128 158 18...

Test 16

Group: 5, 6

Verdict:

input
1000 2000
928772177 816188227 216592201 ...

correct output
991676844 990940224 990685481 ...

user output
928772177 816188227 216592201 ...

Test 17

Group: 5, 6

Verdict:

input
1000 2000
665759876 597950008 615453266 ...

correct output
498801198 498681904 498504321 ...

user output
665759876 597950008 615453266 ...

Test 18

Group: 5, 6

Verdict:

input
500 2000
683288817 784230412 626685186 ...

correct output
497667621 498434895 495465990 ...

user output
683288817 784230412 626685186 ...

Test 19

Group: 5, 6

Verdict:

input
1000 2000
666667000 809309500 571572000 ...

correct output
499499500 499249250 498999000 ...

user output
666667000 809309500 571572000 ...

Test 20

Group: 6

Verdict:

input
100000 200000
861772559 734298084 983382252 ...

correct output
499973914 499985299 499985141 ...

user output
861772559 734298084 983382252 ...

Test 21

Group: 6

Verdict:

input
30000 200000
691834579 617419813 514778075 ...

correct output
499967533 499976270 499969810 ...

user output
691834579 617419813 514778075 ...

Test 22

Group: 6

Verdict:

input
100000 200000
820255000 960780000 741965000 ...

correct output
499995000 499992500 499990000 ...

user output
820255000 960780000 741965000 ...