CSES - Aalto Competitive Programming 2024 - wk3 - Wed - Results
Submission details
Task:Sorting coins
Sender:aalto2024c_002
Submission time:2024-09-18 17:10:45 +0300
Language:C++20
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#20.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#80.00 sdetails
#90.00 sdetails
#10ACCEPTED0.00 sdetails
#110.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#150.00 sdetails
#160.01 sdetails
#17ACCEPTED0.00 sdetails
#180.00 sdetails
#190.00 sdetails
#20ACCEPTED0.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#260.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.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.23 sdetails
#520.23 sdetails
#530.27 sdetails
#540.24 sdetails
#550.23 sdetails
#560.24 sdetails
#570.25 sdetails
#580.26 sdetails
#590.24 sdetails
#600.26 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:48:13: warning: unused variable 'nholes' [-Wunused-variable]
   48 |         int nholes = 0;
      |             ^~~~~~

Code

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int> > coins(n);
    vector<int> holes(m);

    for (int i = 0; i < n; i++) {
        cin >> coins[i].first;
        coins[i].second = i;
    }

    for (int i = 0; i < m; i++) {
        cin >> holes[i];
    }

    sort(coins.begin(), coins.end());

    // solve for 1

    // i is i - 1

    vector< pair<int, int> > res(n, {0, 0});
    for (int i = 0; i < n; i++) res[i].second = coins[i].second;

    int j = 0;
    for (int i = 0; i < n; i++) {


        int current_coin = coins[i].first;

        //cout << current_coin << ',';

        int nholes = 0;
        while (j < m and current_coin > holes[j]) ++j;
        //if (current_coin > holes[j]) --j;

        cout << j  + 1 << endl;


        //if (coins[i].first <= holes[ res[ coins[i - 1].second ].first ]) res[i].first = res[i - 1].first;
        //--j;

        res[i].first = j;

    /*
        if (i != 0)
            res[i].first = res[i - 1].first + nholes;
        else
            res[i].first = nholes;
            */
    }

    sort(res.begin(), res.end(), sort_pred());

    for (int i = 0; i < n; i++) cout <<  res[i].first + 1<< ' ';
    cout << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
1 1
10 

correct output

user output
2

Test 2

Verdict:

input
2 1
5 1 

correct output
2 1 

user output
1
2
2 1 

Test 3

Verdict: ACCEPTED

input
2 3
6 9 
7 3 5 

correct output
1 4 

user output
1
4
1 4 

Test 4

Verdict: ACCEPTED

input
2 1
7 9 

correct output
2 2 

user output
2
2
2 2 

Test 5

Verdict:

input
3 2
7 1 5 
2 5 

correct output
3 1 2 

user output
1
2
3
3 1 2 

Test 6

Verdict:

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

correct output
5 1 5 

user output
1
5
5
5 1 5 

Test 7

Verdict:

input
3 2
1 10 1 
6 7 

correct output
1 3 1 

user output
1
1
3
1 3 1 

Test 8

Verdict:

input
4 4
5 6 9 6 
8 4 10 9 

correct output
1 1 3 1 

user output
1
1
1
3
1 1 3 1 

Test 9

Verdict:

input
4 3
8 2 4 2 
6 9 1 

correct output
2 1 1 1 

user output
1
1
1
2
2 1 1 1 

Test 10

Verdict: ACCEPTED

input
4 3
1 2 4 7 
3 5 8 

correct output
1 1 2 3 

user output
1
1
2
3
1 1 2 3 

Test 11

Verdict:

input
5 3
4 10 10 5 1 
1 9 9 

correct output
2 4 4 2 1 

user output
1
2
2
4
4
...

Test 12

Verdict: ACCEPTED

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

correct output
1 7 7 7 7 

user output
1
7
7
7
7
...

Test 13

Verdict: ACCEPTED

input
5 1
4 5 10 8 5 

correct output
2 2 2 2 2 

user output
2
2
2
2
2
...

Test 14

Verdict: ACCEPTED

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

correct output
2 2 2 2 2 

user output
2
2
2
2
2
...

Test 15

Verdict:

input
5 1
5 5 1 2 4 

correct output
2 2 1 1 1 

user output
1
1
1
2
2
...

Test 16

Verdict:

input
5 8
3 1 2 8 8 
1 3 5 5 5 7 8 9 

correct output
2 1 2 7 7 

user output
1
2
2
7
7
...

Test 17

Verdict: ACCEPTED

input
5 2
5 2 8 10 5 
1 1 

correct output
3 3 3 3 3 

user output
3
3
3
3
3
...

Test 18

Verdict:

input
5 2
3 1 6 8 1 
5 8 

correct output
1 1 2 2 1 

user output
1
1
1
2
2
...

Test 19

Verdict:

input
5 8
5 8 7 7 8 
2 3 7 9 9 9 10 10 

correct output
3 4 3 3 4 

user output
3
3
3
4
4
...

Test 20

Verdict: ACCEPTED

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

correct output
1 1 1 1 1 

user output
1
1
1
1
1
...

Test 21

Verdict:

input
10 16
1 2 7 7 10 9 1 4 6 9 
3 1 5 7 5 8 9 5 6 3 1 2 8 8 3 ...

correct output
1 1 4 4 17 7 1 3 4 7 

user output
1
1
1
3
4
...

Test 22

Verdict:

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

correct output
5 5 3 3 3 3 1 5 3 5 

user output
1
3
3
3
3
...

Test 23

Verdict:

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

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

user output
1
1
1
1
1
...

Test 24

Verdict:

input
10 16
8 4 1 7 3 10 1 8 9 5 
7 3 9 9 9 10 2 10 8 5 8 7 7 8 ...

correct output
3 1 1 1 1 6 1 3 3 1 

user output
1
1
1
1
1
...

Test 25

Verdict:

input
10 11
4 4 4 6 6 3 7 9 6 4 
1 2 3 3 4 4 7 8 9 10 10 

correct output
5 5 5 7 7 3 7 9 7 5 

user output
3
5
5
5
5
...

Test 26

Verdict:

input
10 17
9 10 1 3 6 8 6 9 10 9 
9 2 6 1 2 4 9 3 10 6 1 4 9 4 8...

correct output
1 9 1 1 1 1 1 1 9 1 

user output
1
1
1
1
1
...

Test 27

Verdict:

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

correct output
1 1 6 1 1 6 6 1 6 1 

user output
1
1
1
1
1
...

Test 28

Verdict:

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

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

user output
1
2
4
4
4
...

Test 29

Verdict:

input
10 14
3 9 1 10 7 4 9 6 8 6 
1 1 2 3 3 5 5 6 7 8 9 9 10 10 

correct output
4 11 1 13 9 6 11 8 10 8 

user output
1
4
6
8
8
...

Test 30

Verdict:

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

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

user output
1
1
1
1
1
...

Test 31

Verdict:

input
100 109
670851894 542702872 156237497 ...

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

user output
1
1
1
1
1
...

Test 32

Verdict:

input
100 104
65679420 148186648 745144547 5...

correct output
8 16 75 8 68 22 48 45 56 99 93...

user output
2
3
7
8
8
...

Test 33

Verdict:

input
100 120
327701031 843462639 697056609 ...

correct output
1 10 2 1 1 10 1 6 1 2 1 2 2 2 ...

user output
1
1
1
1
1
...

Test 34

Verdict:

input
100 87
973756781 787585117 426104879 ...

correct output
30 3 3 3 3 3 3 3 7 1 1 1 1 3 3...

user output
1
1
1
1
1
...

Test 35

Verdict:

input
100 30
259467422 179425210 302226641 ...

correct output
10 6 11 26 21 5 4 25 6 25 6 25...

user output
2
2
2
2
3
...

Test 36

Verdict:

input
100 17
619610888 28975240 267230415 3...

correct output
11 2 4 7 18 3 10 11 17 10 3 15...

user output
2
2
3
3
3
...

Test 37

Verdict:

input
100 2
536076934 655217422 133320243 ...

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

user output
1
1
1
1
1
...

Test 38

Verdict:

input
100 33
789380894 994229768 42675899 9...

correct output
1 34 1 1 1 1 1 1 1 1 1 1 1 1 1...

user output
1
1
1
1
1
...

Test 39

Verdict:

input
100 47
246778198 676999670 608531210 ...

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

user output
1
1
1
1
1
...

Test 40

Verdict:

input
100 123
886976100 68201365 172296705 8...

correct output
104 10 23 102 55 94 62 53 10 1...

user output
3
6
6
10
10
...

Test 41

Verdict:

input
200 380
317524454 41051177 567149094 1...

correct output
1 1 4 1 1 14 8 8 8 14 1 8 1 1 ...

user output
1
1
1
1
1
...

Test 42

Verdict:

input
200 46
392347176 726442861 545265216 ...

correct output
17 27 22 17 17 22 24 24 14 17 ...

user output
1
1
1
2
2
...

Test 43

Verdict:

input
200 90
248312993 106444472 194127938 ...

correct output
21 6 15 26 1 32 26 26 68 85 90...

user output
1
1
1
1
2
...

Test 44

Verdict:

input
200 340
798996025 496231366 876215524 ...

correct output
270 170 293 217 337 3 53 124 2...

user output
1
2
3
3
5
...

Test 45

Verdict:

input
200 373
589488280 542132074 375966293 ...

correct output
1 1 1 3 1 1 1 1 3 1 6 1 1 1 6 ...

user output
1
1
1
1
1
...

Test 46

Verdict:

input
200 385
196646115 242041521 295990544 ...

correct output
2 2 2 5 5 5 2 5 24 2 2 13 1 2 ...

user output
1
1
1
1
1
...

Test 47

Verdict:

input
200 171
393795758 726432748 126764724 ...

correct output
64 127 18 63 59 13 8 17 65 1 1...

user output
1
1
1
1
5
...

Test 48

Verdict:

input
200 202
942051979 368818134 268535120 ...

correct output
5 1 1 1 5 1 1 1 1 1 1 1 1 1 5 ...

user output
1
1
1
1
1
...

Test 49

Verdict:

input
200 45
633221062 364986147 972778007 ...

correct output
1 1 46 1 1 1 2 5 1 1 2 1 1 1 1...

user output
1
1
1
1
1
...

Test 50

Verdict:

input
200 338
454221387 88895945 317597498 4...

correct output
142 29 99 134 182 88 235 278 2...

user output
4
4
11
14
15
...

Test 51

Verdict:

input
100000 28757
118267157 851671329 411822891 ...

correct output
1 17 1 1 1 5 1 1 1 1 1 5 1 1 1...

user output
1
1
1
1
1
...

Test 52

Verdict:

input
100000 18305
702302355 6062709 611429541 54...

correct output
12872 122 11266 9987 7473 9155...

user output
1
1
2
3
3
...

Test 53

Verdict:

input
100000 95231
656622458 70589811 632582055 4...

correct output
62527 6715 60175 47354 58575 8...

user output
2
3
3
3
3
...

Test 54

Verdict:

input
100000 30329
45713456 729104659 758685635 8...

correct output
1333 22090 23000 25105 6039 20...

user output
2
2
2
2
4
...

Test 55

Verdict:

input
100000 31228
247919198 225373356 731438419 ...

correct output
1 1 1 1 16 1 1 1 1 1 1 1 1 1 1...

user output
1
1
1
1
1
...

Test 56

Verdict:

input
100000 30512
675116653 115272339 718909731 ...

correct output
20571 3556 21916 12569 11110 2...

user output
1
1
1
3
5
...

Test 57

Verdict:

input
100000 75350
239099439 812355621 986530470 ...

correct output
1 2 203 1 2 1 2 2 1 1 203 17 2...

user output
1
1
1
1
1
...

Test 58

Verdict:

input
100000 87421
916970017 111389270 307679149 ...

correct output
80168 9865 27064 35762 21561 8...

user output
1
2
2
4
4
...

Test 59

Verdict:

input
100000 37351
409368120 919782880 717179531 ...

correct output
15405 34298 26803 6413 9862 63...

user output
1
1
2
4
5
...

Test 60

Verdict:

input
100000 92760
574361642 194853225 729709108 ...

correct output
53251 18025 67482 3845 17916 7...

user output
5
6
6
7
11
...