Submission details
Task:Good grades
Sender:aalto25j_002
Submission time:2025-11-05 18:01:30 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#20.00 sdetails
#3ACCEPTED0.00 sdetails
#40.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#80.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#160.00 sdetails
#17ACCEPTED0.00 sdetails
#180.00 sdetails
#19ACCEPTED0.00 sdetails
#200.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#260.00 sdetails
#27ACCEPTED0.00 sdetails
#280.00 sdetails
#29ACCEPTED0.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#340.00 sdetails
#350.00 sdetails
#360.00 sdetails
#370.00 sdetails
#380.00 sdetails
#390.00 sdetails
#400.00 sdetails
#410.00 sdetails
#420.00 sdetails
#430.00 sdetails
#440.00 sdetails
#450.00 sdetails
#460.00 sdetails
#470.00 sdetails
#480.00 sdetails
#490.00 sdetails
#500.00 sdetails
#510.00 sdetails
#520.00 sdetails
#530.00 sdetails
#540.00 sdetails
#550.00 sdetails
#560.00 sdetails
#570.00 sdetails
#580.00 sdetails
#590.00 sdetails

Code

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define LOOP(i,s,e) for (int64_t i = (s); i < (e); i++)
#define SCAN(...) if (scanf(__VA_ARGS__) == 0) return EXIT_FAILURE

typedef struct p{
    int64_t v;
    int64_t i;
} p;

int comp(const void *a, const void *b){
    p ca = *((p*)a);
    p cb = *((p*)b);
    if (ca.v == cb.v) return 0;
    if (ca.v < cb.v) return -1;
    return 1;
}

int main() {
    int64_t n, k;
    SCAN("%ld %ld", &n, &k);

    p *sorted = (p*) malloc(2 * n * sizeof(p));

    LOOP(i, 0, n){
        SCAN("%ld", &sorted[i].v);
        sorted[i].i=i;
    }


    qsort(sorted, n, sizeof(p), comp);

    int64_t *groups = (int64_t *) malloc((k+1) * sizeof(int64_t));

    // group i goes from groups[i] to groups[i+1]

    LOOP(i, 1, k)
        groups[i] = i;
    groups[0] = 0;
    groups[k] = n;

    int64_t old_smart = 0;
    int64_t smart = 0;
    // bool retest = false;
    LOOP(i, 0, k)
        smart += sorted[groups[i]].v * (groups[i+1]-groups[i]);

    while (old_smart != smart){
        old_smart = smart;
        // increase right
        for(int64_t i = k-2; i >= 0; i--){
            int64_t diff =
                - sorted[groups[i]].v * (groups[i+1]-groups[i])
                + sorted[groups[i]].v * (groups[i+1]-groups[i] + 1)
                - sorted[groups[i+1]].v * (groups[i+2]-groups[i+1])
                + sorted[groups[i+1]+1].v * (groups[i+2]-groups[i+1] - 1);
            // printf("%ld -> %ld : dif = %ld\n", groups[i+1], groups[i+1]+1, diff);
            while(diff >= 0 && groups[i+1] < groups[i+2]){
                groups[i+1]++;
                diff =
                - sorted[groups[i]].v * (groups[i+1]-groups[i])
                + sorted[groups[i]].v * (groups[i+1]-groups[i] + 1)
                - sorted[groups[i+1]].v * (groups[i+2]-groups[i+1])
                + sorted[groups[i+1]+1].v * (groups[i+2]-groups[i+1] - 1);
                // printf("++%ld -> %ld : dif = %ld\n", groups[i+1], groups[i+1]+1, diff);

            }
        }
        // decrease left
        // LOOP(i, 1, k){
        //     int64_t diff =
        //         - sorted[groups[i]].v * (groups[i+1]-groups[i])
        //         + sorted[groups[i]-1].v * (groups[i+1]-groups[i] + 1)
        //         - sorted[groups[i-1]].v * (groups[i]-groups[i-1])
        //         + sorted[groups[i-1]].v * (groups[i]-groups[i-1] - 1);
        //     while(diff >= 0 && groups[i-1] < groups[i]){
        //         groups[i]--;
        //         diff =
        //         - sorted[groups[i]].v * (groups[i+1]-groups[i])
        //         + sorted[groups[i]-1].v * (groups[i+1]-groups[i] + 1)
        //         - sorted[groups[i-1]].v * (groups[i]-groups[i-1])
        //         + sorted[groups[i-1]].v * (groups[i]-groups[i-1] - 1);
        //     }
        // }
        // get number
        smart = 0;
        LOOP(i, 0, k)
            smart += sorted[groups[i]].v * (groups[i+1]-groups[i]);
        // retest = ~retest || (smart != old_smart);
        // eraze empty groups
    }

    int64_t *places = (int64_t*) malloc(n * sizeof(int64_t));
    for(int64_t i = k-1; i > 0; i--){
        printf("groups[%ld] = %ld, groups[%ld] = %ld\n", i, groups[i], i+1, groups[i+1]);
        if (groups[i] == groups[i+1])
            groups[i]--;
    }


    LOOP(g, 0, k){
        LOOP(i, groups[g], groups[g+1]){
            // printf("%ld ", sorted[i].v);
            places[sorted[i].i] = g+1;
        }
        // printf(" |  ");
    }

    // printf("\n");
    LOOP(i, 0, n)
        printf("%ld ", places[i]);
    printf("\n");




    return EXIT_SUCCESS;
}

Test details

Test 1

Verdict: ACCEPTED

input
1 1

correct output

user output

Test 2

Verdict:

input
2 2
7 6 

correct output
2 1 

user output
groups[1] = 1, groups[2] = 2
2 1 

Test 3

Verdict: ACCEPTED

input
2 1
7 7 

correct output
1 1 

user output
1 1 

Test 4

Verdict:

input
2 2
7 1 

correct output
2 1 

user output
groups[1] = 1, groups[2] = 2
2 1 

Test 5

Verdict: ACCEPTED

input
3 1
5 10 8 

correct output
1 1 1 

user output
1 1 1 

Test 6

Verdict: ACCEPTED

input
3 1
6 10 2 

correct output
1 1 1 

user output
1 1 1 

Test 7

Verdict: ACCEPTED

input
4 1
10 10 4 2 

correct output
1 1 1 1 

user output
1 1 1 1 

Test 8

Verdict:

input
4 4
5 1 5 4 

correct output
3 1 4 2 

user output
groups[3] = 4, groups[4] = 4
groups[2] = 2, groups[3] = 3
groups[1] = 1, groups[2] = 2
3 1

...
Truncated

Test 9

Verdict:

input
4 2
1 6 7 1 

correct output
1 2 2 1 

user output
groups[1] = 2, groups[2] = 4
1 2 2 1 

Test 10

Verdict:

input
5 3
6 8 9 7 9 

correct output
1 2 3 1 3 

user output
groups[2] = 3, groups[3] = 5
groups[1] = 2, groups[2] = 3
1 2 3 1 3 

Test 11

Verdict:

input
5 3
10 8 10 1 2 

correct output
3 2 3 1 1 

user output
groups[2] = 2, groups[3] = 5
groups[1] = 1, groups[2] = 2
3 3 3 1 2 

Test 12

Verdict:

input
5 3
2 1 10 6 10 

correct output
1 1 3 2 3 

user output
groups[2] = 3, groups[3] = 5
groups[1] = 2, groups[2] = 3
1 1 3 2 3 

Test 13

Verdict:

input
5 3
1 8 9 3 2 

correct output
1 3 3 2 1 

user output
groups[2] = 3, groups[3] = 5
groups[1] = 2, groups[2] = 3
1 3 3 2 1 

Test 14

Verdict:

input
5 5
10 6 2 10 9 

correct output
4 2 1 5 3 

user output
groups[4] = 5, groups[5] = 5
groups[3] = 3, groups[4] = 4
groups[2] = 2, groups[3] = 3
gro

...
Truncated

Test 15

Verdict:

input
5 2
1 9 9 3 4 

correct output
1 2 2 1 1 

user output
groups[1] = 3, groups[2] = 5
1 2 2 1 1 

Test 16

Verdict:

input
5 5
10 4 3 9 1 

correct output
5 3 2 4 1 

user output
groups[4] = 4, groups[5] = 5
groups[3] = 3, groups[4] = 4
groups[2] = 2, groups[3] = 3
gro

...
Truncated

Test 17

Verdict: ACCEPTED

input
5 1
3 8 4 5 10 

correct output
1 1 1 1 1 

user output
1 1 1 1 1 

Test 18

Verdict:

input
5 5
1 10 3 9 4 

correct output
1 5 2 4 3 

user output
groups[4] = 4, groups[5] = 5
groups[3] = 3, groups[4] = 4
groups[2] = 2, groups[3] = 3
gro

...
Truncated

Test 19

Verdict: ACCEPTED

input
5 1
4 6 5 5 1 

correct output
1 1 1 1 1 

user output
1 1 1 1 1 

Test 20

Verdict:

input
10 6
6 8 9 7 9 6 9 5 7 7 

correct output
2 4 5 3 5 2 6 1 3 3 

user output
groups[5] = 7, groups[6] = 10
groups[4] = 6, groups[5] = 7
groups[3] = 6, groups[4] = 6
gr

...
Truncated

Test 21

Verdict:

input
10 5
10 8 10 1 2 4 10 2 3 1 

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

user output
groups[4] = 7, groups[5] = 10
groups[3] = 6, groups[4] = 7
groups[2] = 5, groups[3] = 6
gr

...
Truncated

Test 22

Verdict:

input
10 5
2 1 10 6 10 5 5 5 4 4 

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

user output
groups[4] = 4, groups[5] = 10
groups[3] = 4, groups[4] = 4
groups[2] = 2, groups[3] = 3
gr

...
Truncated

Test 23

Verdict:

input
10 6
1 8 9 3 2 6 6 9 5 9 

correct output
1 5 6 2 1 4 4 6 3 6 

user output
groups[5] = 7, groups[6] = 10
groups[4] = 4, groups[5] = 7
groups[3] = 3, groups[4] = 4
gr

...
Truncated

Test 24

Verdict:

input
10 10
10 6 2 10 9 8 7 7 6 3 

correct output
9 3 1 10 8 7 5 6 4 2 

user output
groups[9] = 10, groups[10] = 1...
Truncated

Test 25

Verdict:

input
10 3
1 9 9 3 4 10 10 5 1 7 

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

user output
groups[2] = 6, groups[3] = 10
groups[1] = 3, groups[2] = 6
1 3 3 1 2 3 3 2 1 2 

Test 26

Verdict:

input
10 9
10 4 3 9 1 1 4 2 10 6 

correct output
8 4 3 7 1 1 5 2 9 6 

user output
groups[8] = 8, groups[9] = 10
groups[7] = 7, groups[8] = 8
groups[6] = 6, groups[7] = 7
gr

...
Truncated

Test 27

Verdict: ACCEPTED

input
10 1
3 8 4 5 10 8 5 10 4 6 

correct output
1 1 1 1 1 1 1 1 1 1 

user output
1 1 1 1 1 1 1 1 1 1 

Test 28

Verdict:

input
10 9
1 10 3 9 4 6 9 3 5 1 

correct output
1 9 2 7 4 6 8 3 5 1 

user output
groups[8] = 9, groups[9] = 10
groups[7] = 7, groups[8] = 9
groups[6] = 6, groups[7] = 7
gr

...
Truncated

Test 29

Verdict: ACCEPTED

input
10 1
4 6 5 5 1 2 4 2 1 3 

correct output
1 1 1 1 1 1 1 1 1 1 

user output
1 1 1 1 1 1 1 1 1 1 

Test 30

Verdict:

input
100 55
636562060 767928734 906523441 ...

correct output
32 42 50 33 51 29 50 23 35 37 ...

user output
groups[54] = 54, groups[55] = ...
Truncated

Test 31

Verdict:

input
100 42
773442532 122816 137572579 324...

correct output
34 1 8 16 9 13 6 20 10 19 18 3...

user output
groups[41] = 59, groups[42] = ...
Truncated

Test 32

Verdict:

input
100 44
198730372 27838076 590195590 4...

correct output
9 1 28 21 23 20 15 16 7 10 36 ...

user output
groups[43] = 48, groups[44] = ...
Truncated

Test 33

Verdict:

input
100 56
75940263 760367935 901888417 3...

correct output
6 44 51 19 8 33 36 54 29 54 1 ...

user output
groups[55] = 63, groups[56] = ...
Truncated

Test 34

Verdict:

input
100 97
967034924 587586158 185430194 ...

correct output
94 59 19 88 79 67 77 64 27 15 ...

user output
groups[96] = 98, groups[97] = ...
Truncated

Test 35

Verdict:

input
100 23
59249204 934941692 892631472 2...

correct output
2 22 21 6 10 23 12 3 15 11 19 ...

user output
groups[22] = 35, groups[23] = ...
Truncated

Test 36

Verdict:

input
100 90
356460601 224848374 881788059 ...

correct output
23 14 83 4 1 28 8 54 7 48 56 3...

user output
groups[89] = 89, groups[90] = ...
Truncated

Test 37

Verdict:

input
100 8
244103474 837431431 342493822 ...

correct output
2 7 3 5 7 5 3 6 3 5 1 1 5 3 1 ...

user output
groups[7] = 22, groups[8] = 10...
Truncated

Test 38

Verdict:

input
100 88
11934038 257096283 933290530 4...

correct output
1 24 83 40 56 80 23 44 1 62 46...

user output
groups[87] = 90, groups[88] = ...
Truncated

Test 39

Verdict:

input
100 2
391337048 538883744 535937150 ...

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

user output
groups[1] = 2, groups[2] = 100
2 2 2 2 1 2 2 2 1 2 2 2 2 2 2 ...
Truncated

Test 40

Verdict:

input
200 110
636562060 767928734 906523441 ...

correct output
69 86 99 70 101 61 100 47 74 7...

user output
groups[109] = 120, groups[110]...
Truncated

Test 41

Verdict:

input
200 84
773442532 122816 137572579 324...

correct output
66 1 14 28 16 23 11 36 18 35 3...

user output
groups[83] = 94, groups[84] = ...
Truncated

Test 42

Verdict:

input
200 88
198730372 27838076 590195590 4...

correct output
17 3 53 42 45 40 29 30 13 18 6...

user output
groups[87] = 93, groups[88] = ...
Truncated

Test 43

Verdict:

input
200 111
75940263 760367935 901888417 3...

correct output
8 85 100 35 14 62 71 106 51 10...

user output
groups[110] = 116, groups[111]...
Truncated

Test 44

Verdict:

input
200 194
967034924 587586158 185430194 ...

correct output
185 114 39 173 151 128 147 124...

user output
groups[193] = 195, groups[194]...
Truncated

Test 45

Verdict:

input
200 45
59249204 934941692 892631472 2...

correct output
3 43 41 11 19 45 25 5 30 21 37...

user output
groups[44] = 75, groups[45] = ...
Truncated

Test 46

Verdict:

input
200 179
356460601 224848374 881788059 ...

correct output
54 33 162 8 4 61 15 113 14 99 ...

user output
groups[178] = 186, groups[179]...
Truncated

Test 47

Verdict:

input
200 16
244103474 837431431 342493822 ...

correct output
4 14 6 8 13 9 6 10 5 10 2 2 8 ...

user output
groups[15] = 42, groups[16] = ...
Truncated

Test 48

Verdict:

input
200 175
11934038 257096283 933290530 4...

correct output
2 40 165 67 105 157 37 77 2 11...

user output
groups[174] = 188, groups[175]...
Truncated

Test 49

Verdict:

input
200 3
391337048 538883744 535937150 ...

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

user output
groups[2] = 32, groups[3] = 20...
Truncated

Test 50

Verdict:

input
500 275
636562060 767928734 906523441 ...

correct output
176 215 251 178 254 161 252 12...

user output
groups[274] = 294, groups[275]...
Truncated

Test 51

Verdict:

input
500 209
773442532 122816 137572579 324...

correct output
163 1 31 72 37 57 23 89 45 87 ...

user output
groups[208] = 216, groups[209]...
Truncated

Test 52

Verdict:

input
500 218
198730372 27838076 590195590 4...

correct output
42 8 130 102 113 97 73 75 34 4...

user output
groups[217] = 222, groups[218]...
Truncated

Test 53

Verdict:

input
500 276
75940263 760367935 901888417 3...

correct output
20 205 249 85 32 149 165 267 1...

user output
groups[275] = 300, groups[276]...
Truncated

Test 54

Verdict:

input
500 484
967034924 587586158 185430194 ...

correct output
469 290 97 438 372 322 367 317...

user output
groups[483] = 486, groups[484]...
Truncated

Test 55

Verdict:

input
500 111
59249204 934941692 892631472 2...

correct output
5 104 100 24 42 109 55 9 70 46...

user output
groups[110] = 145, groups[111]...
Truncated

Test 56

Verdict:

input
500 447
356460601 224848374 881788059 ...

correct output
154 88 394 30 18 168 46 279 43...

user output
groups[446] = 458, groups[447]...
Truncated

Test 57

Verdict:

input
500 39
244103474 837431431 342493822 ...

correct output
9 33 13 18 31 19 13 23 11 21 3...

user output
groups[38] = 79, groups[39] = ...
Truncated

Test 58

Verdict:

input
500 437
11934038 257096283 933290530 4...

correct output
7 101 407 167 251 388 97 191 7...

user output
groups[436] = 444, groups[437]...
Truncated

Test 59

Verdict:

input
500 6
391337048 538883744 535937150 ...

correct output
3 4 4 4 1 2 3 2 1 2 6 3 2 2 2 ...

user output
groups[5] = 63, groups[6] = 50...
Truncated