CSES - Aalto Competitive Programming 2024 - wk3 - Wed

CSES - Aalto Competitive Programming 2024 - wk3 - Wed - Results

Submission details
Task:	Sorting coins
Sender:	aalto2024c_010
Submission time:	2024-09-18 16:23:01 +0300
Language:	C++ (C++17)
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.00 s	details
#3	ACCEPTED	0.00 s	details
#4	ACCEPTED	0.00 s	details
#5	ACCEPTED	0.00 s	details
#6	ACCEPTED	0.00 s	details
#7	ACCEPTED	0.00 s	details
#8	ACCEPTED	0.00 s	details
#9	ACCEPTED	0.00 s	details
#10	ACCEPTED	0.00 s	details
#11	ACCEPTED	0.00 s	details
#12	ACCEPTED	0.00 s	details
#13	ACCEPTED	0.00 s	details
#14	ACCEPTED	0.00 s	details
#15	ACCEPTED	0.00 s	details
#16	ACCEPTED	0.00 s	details
#17	ACCEPTED	0.00 s	details
#18	ACCEPTED	0.00 s	details
#19	ACCEPTED	0.00 s	details
#20	ACCEPTED	0.00 s	details
#21	ACCEPTED	0.00 s	details
#22	ACCEPTED	0.00 s	details
#23	ACCEPTED	0.00 s	details
#24	ACCEPTED	0.00 s	details
#25	ACCEPTED	0.00 s	details
#26	ACCEPTED	0.00 s	details
#27	ACCEPTED	0.00 s	details
#28	ACCEPTED	0.00 s	details
#29	ACCEPTED	0.00 s	details
#30	ACCEPTED	0.00 s	details
#31	ACCEPTED	0.00 s	details
#32	ACCEPTED	0.00 s	details
#33	ACCEPTED	0.00 s	details
#34	ACCEPTED	0.00 s	details
#35	ACCEPTED	0.00 s	details
#36	ACCEPTED	0.00 s	details
#37	ACCEPTED	0.00 s	details
#38	ACCEPTED	0.00 s	details
#39	ACCEPTED	0.00 s	details
#40	ACCEPTED	0.00 s	details
#41	ACCEPTED	0.00 s	details
#42	ACCEPTED	0.00 s	details
#43	ACCEPTED	0.00 s	details
#44	ACCEPTED	0.00 s	details
#45	ACCEPTED	0.00 s	details
#46	ACCEPTED	0.00 s	details
#47	ACCEPTED	0.00 s	details
#48	ACCEPTED	0.00 s	details
#49	ACCEPTED	0.00 s	details
#50	ACCEPTED	0.00 s	details
#51	ACCEPTED	0.04 s	details
#52	ACCEPTED	0.04 s	details
#53	ACCEPTED	0.05 s	details
#54	ACCEPTED	0.04 s	details
#55	ACCEPTED	0.04 s	details
#56	ACCEPTED	0.04 s	details
#57	ACCEPTED	0.04 s	details
#58	ACCEPTED	0.05 s	details
#59	ACCEPTED	0.05 s	details
#60	ACCEPTED	0.05 s	details

Code

// ~/.vim/cpp_template.cpp
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define REP(i,a,b) for (int i = a; i < b; i++)

using namespace std;

template <typename T>
void pV(const std::vector<T>& vec, const std::string& label = "Vector") {
    std::cout << label << ": [ ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << "]" << std::endl;
}


using namespace std;


void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {
    if ((*visited)[s]) return;
    (*visited)[s] = true;
    // process node s


    for (auto u: (*adj)[s]) {
        dfs(u, visited, adj);
    }
}
/*
vector<int> adj[N];                                                          
vector<bool> visited(N, false);
int u, v;
for(int i = 0; i < M;i++){
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
*/

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // Your code starts here

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    vector<int> b(m);
    vector<pair<int, int>> sorted_coins(n);
    vector<int> res(n);

    REP(i, 0, n){
        cin >> a[i];
        sorted_coins[i] = {a[i], i};
    }

    REP(i, 0, m){
        cin >> b[i];
    }

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

    int hole_index = 0;
    REP(i, 0, n) {
        while (hole_index < m && sorted_coins[i].first > b[hole_index]) {
            hole_index++;
        }
        if (hole_index < m) {
            res[sorted_coins[i].second] = hole_index + 1; 
        } else {
            res[sorted_coins[i].second] = m + 1;
        }
    }

    for (int r : res) {
        cout << r << " ";
    }
    cout << endl;

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`1 1 10 7` view save

correct output
`2` view save

user output
`2` view save

Test 2

Verdict: ACCEPTED

input
`2 1 5 1 2` view save

correct output
`2 1` view save

user output
`2 1` view save

Test 3

Verdict: ACCEPTED

input
`2 3 6 9 7 3 5` view save

correct output
`1 4` view save

user output
`1 4` view save

Test 4

Verdict: ACCEPTED

input
`2 1 7 9 3` view save

correct output
`2 2` view save

user output
`2 2` view save

Test 5

Verdict: ACCEPTED

input
`3 2 7 1 5 2 5` view save

correct output
`3 1 2` view save

user output
`3 1 2` view save

Test 6

Verdict: ACCEPTED

input
`3 6 8 1 7 2 5 2 3 8 9` view save

correct output
`5 1 5` view save

user output
`5 1 5` view save

Test 7

Verdict: ACCEPTED

input
`3 2 1 10 1 6 7` view save

correct output
`1 3 1` view save

user output
`1 3 1` view save

Test 8

Verdict: ACCEPTED

input
`4 4 5 6 9 6 8 4 10 9` view save

correct output
`1 1 3 1` view save

user output
`1 1 3 1` view save

Test 9

Verdict: ACCEPTED

input
`4 3 8 2 4 2 6 9 1` view save

correct output
`2 1 1 1` view save

user output
`2 1 1 1` view save

Test 10

Verdict: ACCEPTED

input
`4 3 1 2 4 7 3 5 8` view save

correct output
`1 1 2 3` view save

user output
`1 1 2 3` view save

Test 11

Verdict: ACCEPTED

input
`5 3 4 10 10 5 1 1 9 9` view save

correct output
`2 4 4 2 1` view save

user output
`2 4 4 2 1` view save

Test 12

Verdict: ACCEPTED

input
`5 9 1 6 7 5 6 1 1 2 3 4 4 9 10 10` view save

correct output
`1 7 7 7 7` view save

user output
`1 7 7 7 7` view save

Test 13

Verdict: ACCEPTED

input
`5 1 4 5 10 8 5 3` view save

correct output
`2 2 2 2 2` view save

user output
`2 2 2 2 2` view save

Test 14

Verdict: ACCEPTED

input
`5 9 7 5 8 5 5 1 10 3 9 4 6 9 3 5` view save

correct output
`2 2 2 2 2` view save

user output
`2 2 2 2 2` view save

Test 15

Verdict: ACCEPTED

input
`5 1 5 5 1 2 4 4` view save

correct output
`2 2 1 1 1` view save

user output
`2 2 1 1 1` view save

Test 16

Verdict: ACCEPTED

input
`5 8 3 1 2 8 8 1 3 5 5 5 7 8 9` view save

correct output
`2 1 2 7 7` view save

user output
`2 1 2 7 7` view save

Test 17

Verdict: ACCEPTED

input
`5 2 5 2 8 10 5 1 1` view save

correct output
`3 3 3 3 3` view save

user output
`3 3 3 3 3` view save

Test 18

Verdict: ACCEPTED

input
`5 2 3 1 6 8 1 5 8` view save

correct output
`1 1 2 2 1` view save

user output
`1 1 2 2 1` view save

Test 19

Verdict: ACCEPTED

input
`5 8 5 8 7 7 8 2 3 7 9 9 9 10 10` view save

correct output
`3 4 3 3 4` view save

user output
`3 4 3 3 4` view save

Test 20

Verdict: ACCEPTED

input
`5 6 4 3 10 3 6 10 8 7 9 4 1` view save

correct output
`1 1 1 1 1` view save

user output
`1 1 1 1 1` view save

Test 21

Verdict: ACCEPTED

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 ...` view save

correct output
`1 1 4 4 17 7 1 3 4 7` view save

user output
`1 1 4 4 17 7 1 3 4 7` view save

Test 22

Verdict: ACCEPTED

input
`10 4 8 10 5 2 5 3 1 9 5 9 1 1 7 5` view save

correct output
`5 5 3 3 3 3 1 5 3 5` view save

user output
`5 5 3 3 3 3 1 5 3 5` view save

Test 23

Verdict: ACCEPTED

input
`10 4 6 8 1 4 10 1 10 3 1 1 5 8 9 3` view save

correct output
`2 2 1 1 5 1 5 1 1 1` view save

user output
`2 2 1 1 5 1 5 1 1 1` view save

Test 24

Verdict: ACCEPTED

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 ...` view save

correct output
`3 1 1 1 1 6 1 3 3 1` view save

user output
`3 1 1 1 1 6 1 3 3 1` view save

Test 25

Verdict: ACCEPTED

input
`10 11 4 4 4 6 6 3 7 9 6 4 1 2 3 3 4 4 7 8 9 10 10` view save

correct output
`5 5 5 7 7 3 7 9 7 5` view save

user output
`5 5 5 7 7 3 7 9 7 5` view save

Test 26

Verdict: ACCEPTED

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...` view save

correct output
`1 9 1 1 1 1 1 1 9 1` view save

user output
`1 9 1 1 1 1 1 1 9 1` view save

Test 27

Verdict: ACCEPTED

input
`10 5 2 4 8 3 2 7 7 2 9 1 4 6 1 6 4` view save

correct output
`1 1 6 1 1 6 6 1 6 1` view save

user output
`1 1 6 1 1 6 6 1 6 1` view save

Test 28

Verdict: ACCEPTED

input
`10 6 8 5 7 2 7 3 6 7 1 9 1 2 2 6 9 9` view save

correct output
`5 4 5 2 5 4 4 5 1 5` view save

user output
`5 4 5 2 5 4 4 5 1 5` view save

Test 29

Verdict: ACCEPTED

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` view save

correct output
`4 11 1 13 9 6 11 8 10 8` view save

user output
`4 11 1 13 9 6 11 8 10 8` view save

Test 30

Verdict: ACCEPTED

input
`10 2 3 8 2 3 4 7 1 1 7 2 5 8` view save

correct output
`1 2 1 1 1 2 1 1 2 1` view save

user output
`1 2 1 1 1 2 1 1 2 1` view save

Test 31

Verdict: ACCEPTED

input
`100 109 670851894 542702872 156237497 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` Truncated

Test 32

Verdict: ACCEPTED

input
`100 104 65679420 148186648 745144547 5...` view save

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

user output
`8 16 75 8 68 22 48 45 56 99 93...` Truncated

Test 33

Verdict: ACCEPTED

input
`100 120 327701031 843462639 697056609 ...` view save

correct output
`1 10 2 1 1 10 1 6 1 2 1 2 2 2 ...` view save

user output
`1 10 2 1 1 10 1 6 1 2 1 2 2 2 ...` Truncated

Test 34

Verdict: ACCEPTED

input
`100 87 973756781 787585117 426104879 ...` view save

correct output
`30 3 3 3 3 3 3 3 7 1 1 1 1 3 3...` view save

user output
`30 3 3 3 3 3 3 3 7 1 1 1 1 3 3...` Truncated

Test 35

Verdict: ACCEPTED

input
`100 30 259467422 179425210 302226641 ...` view save

correct output
`10 6 11 26 21 5 4 25 6 25 6 25...` view save

user output
`10 6 11 26 21 5 4 25 6 25 6 25...` Truncated

Test 36

Verdict: ACCEPTED

input
`100 17 619610888 28975240 267230415 3...` view save

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

user output
`11 2 4 7 18 3 10 11 17 10 3 15...` Truncated

Test 37

Verdict: ACCEPTED

input
`100 2 536076934 655217422 133320243 ...` view save

correct output
`1 1 1 3 3 3 1 3 1 3 1 3 1 1 3 ...` view save

user output
`1 1 1 3 3 3 1 3 1 3 1 3 1 1 3 ...` Truncated

Test 38

Verdict: ACCEPTED

input
`100 33 789380894 994229768 42675899 9...` view save

correct output
`1 34 1 1 1 1 1 1 1 1 1 1 1 1 1...` view save

user output
`1 34 1 1 1 1 1 1 1 1 1 1 1 1 1...` Truncated

Test 39

Verdict: ACCEPTED

input
`100 47 246778198 676999670 608531210 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` Truncated

Test 40

Verdict: ACCEPTED

input
`100 123 886976100 68201365 172296705 8...` view save

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

user output
`104 10 23 102 55 94 62 53 10 1...` Truncated

Test 41

Verdict: ACCEPTED

input
`200 380 317524454 41051177 567149094 1...` view save

correct output
`1 1 4 1 1 14 8 8 8 14 1 8 1 1 ...` view save

user output
`1 1 4 1 1 14 8 8 8 14 1 8 1 1 ...` Truncated

Test 42

Verdict: ACCEPTED

input
`200 46 392347176 726442861 545265216 ...` view save

correct output
`17 27 22 17 17 22 24 24 14 17 ...` view save

user output
`17 27 22 17 17 22 24 24 14 17 ...` Truncated

Test 43

Verdict: ACCEPTED

input
`200 90 248312993 106444472 194127938 ...` view save

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

user output
`21 6 15 26 1 32 26 26 68 85 90...` Truncated

Test 44

Verdict: ACCEPTED

input
`200 340 798996025 496231366 876215524 ...` view save

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

user output
`270 170 293 217 337 3 53 124 2...` Truncated

Test 45

Verdict: ACCEPTED

input
`200 373 589488280 542132074 375966293 ...` view save

correct output
`1 1 1 3 1 1 1 1 3 1 6 1 1 1 6 ...` view save

user output
`1 1 1 3 1 1 1 1 3 1 6 1 1 1 6 ...` Truncated

Test 46

Verdict: ACCEPTED

input
`200 385 196646115 242041521 295990544 ...` view save

correct output
`2 2 2 5 5 5 2 5 24 2 2 13 1 2 ...` view save

user output
`2 2 2 5 5 5 2 5 24 2 2 13 1 2 ...` Truncated

Test 47

Verdict: ACCEPTED

input
`200 171 393795758 726432748 126764724 ...` view save

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

user output
`64 127 18 63 59 13 8 17 65 1 1...` Truncated

Test 48

Verdict: ACCEPTED

input
`200 202 942051979 368818134 268535120 ...` view save

correct output
`5 1 1 1 5 1 1 1 1 1 1 1 1 1 5 ...` view save

user output
`5 1 1 1 5 1 1 1 1 1 1 1 1 1 5 ...` Truncated

Test 49

Verdict: ACCEPTED

input
`200 45 633221062 364986147 972778007 ...` view save

correct output
`1 1 46 1 1 1 2 5 1 1 2 1 1 1 1...` view save

user output
`1 1 46 1 1 1 2 5 1 1 2 1 1 1 1...` Truncated

Test 50

Verdict: ACCEPTED

input
`200 338 454221387 88895945 317597498 4...` view save

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

user output
`142 29 99 134 182 88 235 278 2...` Truncated

Test 51

Verdict: ACCEPTED

input
`100000 28757 118267157 851671329 411822891 ...` view save

correct output
`1 17 1 1 1 5 1 1 1 1 1 5 1 1 1...` view save

user output
`1 17 1 1 1 5 1 1 1 1 1 5 1 1 1...` Truncated

Test 52

Verdict: ACCEPTED

input
`100000 18305 702302355 6062709 611429541 54...` view save

correct output
`12872 122 11266 9987 7473 9155...` view save

user output
`12872 122 11266 9987 7473 9155...` Truncated

Test 53

Verdict: ACCEPTED

input
`100000 95231 656622458 70589811 632582055 4...` view save

correct output
`62527 6715 60175 47354 58575 8...` view save

user output
`62527 6715 60175 47354 58575 8...` Truncated

Test 54

Verdict: ACCEPTED

input
`100000 30329 45713456 729104659 758685635 8...` view save

correct output
`1333 22090 23000 25105 6039 20...` view save

user output
`1333 22090 23000 25105 6039 20...` Truncated

Test 55

Verdict: ACCEPTED

input
`100000 31228 247919198 225373356 731438419 ...` view save

correct output
`1 1 1 1 16 1 1 1 1 1 1 1 1 1 1...` view save

user output
`1 1 1 1 16 1 1 1 1 1 1 1 1 1 1...` Truncated

Test 56

Verdict: ACCEPTED

input
`100000 30512 675116653 115272339 718909731 ...` view save

correct output
`20571 3556 21916 12569 11110 2...` view save

user output
`20571 3556 21916 12569 11110 2...` Truncated

Test 57

Verdict: ACCEPTED

input
`100000 75350 239099439 812355621 986530470 ...` view save

correct output
`1 2 203 1 2 1 2 2 1 1 203 17 2...` view save

user output
`1 2 203 1 2 1 2 2 1 1 203 17 2...` Truncated

Test 58

Verdict: ACCEPTED

input
`100000 87421 916970017 111389270 307679149 ...` view save

correct output
`80168 9865 27064 35762 21561 8...` view save

user output
`80168 9865 27064 35762 21561 8...` Truncated

Test 59

Verdict: ACCEPTED

input
`100000 37351 409368120 919782880 717179531 ...` view save

correct output
`15405 34298 26803 6413 9862 63...` view save

user output
`15405 34298 26803 6413 9862 63...` Truncated

Test 60

Verdict: ACCEPTED

input
`100000 92760 574361642 194853225 729709108 ...` view save

correct output
`53251 18025 67482 3845 17916 7...` view save

user output
`53251 18025 67482 3845 17916 7...` Truncated

Aalto Competitive Programming 2024 - wk3 - Wed

Sorting coins

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Tasks

Submissions (aalto2024c_010)