CSES - Aalto Competitive Programming 2024 - wk3 - Wed

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

Submission details
Task:	Sorting coins
Sender:	aalto2024c_009
Submission time:	2024-09-18 17:48:09 +0300
Language:	C++ (C++11)
Status:	READY
Result:	RUNTIME ERROR

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

Code

#include <bits/stdc++.h>

using namespace std;
#define int long long

// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>

// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===

signed main() {
    
    int n, m; // coins, holes
    cin >> n >> m;

    vector<int> r_coins;
    vector<int> r_holes;
    

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        r_coins.push_back(a);
    }
    
    for (int i = 0; i < m; i++) {
        int b;
        cin >> b;
        r_holes.push_back(b);
    }


    // find max to save time: 
    int max_hole = *std::max_element(r_holes.begin(), r_holes.end());

    // find first occurrence of every hole radius and save to array
    const int INF = 10e9+5;
    vector<int> first_occurrence(10e5+1, INF);
    
    for (int i = 0; i < m; i++) 
    {

        if (first_occurrence[r_holes[i]] == INF) {
            first_occurrence[r_holes[i]] = i; // set index starting from 1

            int idx = r_holes[i] - 1;
            // also set first_occurrence for all smaller numbers
            while(idx > 0) {
                if (first_occurrence[idx] == INF) {
                    first_occurrence[idx] = i;
                }
                idx--;
            }
        }
    }

    // dbg(first_occurrence);


    // TODO: first occurrence is not enough, bc there could be a bigger hole first

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

        int coin = r_coins[i];

        // try max first
        if (coin > max_hole) {
            cout << m+1 << " ";
        }
        else {
            while (first_occurrence[coin] == INF) { coin++; }
            cout << first_occurrence[coin] + 1 << " ";
        }
    }


    // for (auto c : r_coins) {
    //     if (c > max_hole) cout << m+1 << " ";
    //     for (int i = 0; i < m; i++) {
    //         if (c <= r_holes[i]) {
    //             cout << i+1 << " ";
    //             break;
    //         }
    //     }
    // }

    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: RUNTIME ERROR

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
(empty)

Test 32

Verdict: RUNTIME ERROR

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
(empty)

Test 33

Verdict: RUNTIME ERROR

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
(empty)

Test 34

Verdict: RUNTIME ERROR

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
(empty)

Test 35

Verdict: RUNTIME ERROR

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
(empty)

Test 36

Verdict: RUNTIME ERROR

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
(empty)

Test 37

Verdict: RUNTIME ERROR

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
(empty)

Test 38

Verdict: RUNTIME ERROR

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
(empty)

Test 39

Verdict: RUNTIME ERROR

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
(empty)

Test 40

Verdict: RUNTIME ERROR

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
(empty)

Test 41

Verdict: RUNTIME ERROR

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
(empty)

Test 42

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 43

Verdict: RUNTIME ERROR

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
(empty)

Test 44

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 45

Verdict: RUNTIME ERROR

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
(empty)

Test 46

Verdict: RUNTIME ERROR

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
(empty)

Test 47

Verdict: RUNTIME ERROR

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
(empty)

Test 48

Verdict: RUNTIME ERROR

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
(empty)

Test 49

Verdict: RUNTIME ERROR

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
(empty)

Test 50

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 51

Verdict: RUNTIME ERROR

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
(empty)

Test 52

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 53

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 54

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 55

Verdict: RUNTIME ERROR

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
(empty)

Test 56

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 57

Verdict: RUNTIME ERROR

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
(empty)

Test 58

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 59

Verdict: RUNTIME ERROR

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

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

user output
(empty)

Test 60

Verdict: RUNTIME ERROR

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

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

user output
(empty)

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_009)