CSES - UKIEPC 2017

Submission details
Task:	Knightsbridge Rises
Sender:	Hannes Ihalainen
Submission time:	2017-10-31 19:39:05 +0200
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.05 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.04 s	details
#4	ACCEPTED	0.05 s	details
#5	ACCEPTED	0.04 s	details
#6	ACCEPTED	0.04 s	details
#7	ACCEPTED	0.04 s	details
#8	ACCEPTED	0.04 s	details
#9	ACCEPTED	0.03 s	details
#10	ACCEPTED	0.04 s	details
#11	ACCEPTED	0.04 s	details
#12	ACCEPTED	0.04 s	details
#13	ACCEPTED	0.05 s	details
#14	ACCEPTED	0.04 s	details
#15	ACCEPTED	0.03 s	details
#16	ACCEPTED	0.05 s	details
#17	ACCEPTED	0.04 s	details
#18	ACCEPTED	0.05 s	details
#19	ACCEPTED	0.03 s	details
#20	ACCEPTED	0.04 s	details
#21	ACCEPTED	0.06 s	details
#22	ACCEPTED	0.04 s	details
#23	ACCEPTED	0.04 s	details
#24	ACCEPTED	0.04 s	details
#25	ACCEPTED	0.05 s	details
#26	ACCEPTED	0.05 s	details
#27	ACCEPTED	0.02 s	details
#28	ACCEPTED	0.04 s	details
#29	ACCEPTED	0.04 s	details
#30	ACCEPTED	0.03 s	details
#31	ACCEPTED	0.04 s	details
#32	ACCEPTED	0.04 s	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:74:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < piles[min_ind].size(); ++j) {
                                            ^

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
const int inf = 1e9;
int main() {
	int n;
	std::cin >> n;
	// weight, carry capacity, index
	std::vector<std::pair<int, std::pair<int, int>>> cranes;
	for (int i = 0; i < n; ++i) {
		int weight, carry;
		std::cin >> weight >> carry;
		cranes.push_back({weight, {carry, i}});
	}
	std::sort(cranes.begin(), cranes.end());
	int m;
	std::cin >> m;
	std::vector<std::vector<int>> piles (m);
	std::vector<int> maximums (m, 0);
	std::vector<bool> used (m, 0);
	std::vector<int> needed (m);
	for (int i = 0; i < m; ++i) {
		std::cin >> needed[i];
	}
	for (int i = 0; i < n; ++i) {
		int low = cranes[i].first;
		int high = cranes[i].second.first;
		int index = cranes[i].second.second;
		int min_ind = -1;
		int min_weight = inf;
		for (int j = 0; j < m; ++j) {
			if ( (maximums[j] >= low) && (maximums[j] < min_weight) ) {
				min_weight = maximums[j];
				min_ind = j;
			}
		}
		if ( (min_ind != -1) && (high > maximums[min_ind]) ) {
			maximums[min_ind] = high;
			piles[min_ind].push_back(index);
		}
	}
	bool can = true;
	for (int i = 0; i < m; ++i) {
		int min_ind = -1;
		int min_weight = inf;
		for (int j = 0; j < m; ++j) {
			if ((!used[j]) && (maximums[j] >= needed[i]) && (maximums[j] < min_weight)) {
				min_ind = j;
				min_weight = maximums[j];
			}
		}
		if (min_ind != -1) {
			used[min_ind] = true;
		} else {
			can = false;
			break;
		}
	}
	if (can) {
		for (int i = 0; i < m; ++i) {
			used[i] = false;
		}
		for (int i = 0; i < m; ++i) {
			int min_ind = -1;
			int min_weight = inf;
			for (int j = 0; j < m; ++j) {
				if ((!used[j]) && (maximums[j] >= needed[i]) && (maximums[j] < min_weight)) {
					min_ind = j;
					min_weight = maximums[j];
				}
			}
			used[min_ind] = true;
			for (int j = 0; j < piles[min_ind].size(); ++j) {
				std::cout << (piles[min_ind][j] + 1) << ' ';
			}
			std::cout << '\n';
		}
	} else {
		std::cout << "impossible\n";
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
`100 1661 4448 0 1 6482 8949 0 2456 ...` view save

correct output
`4 22 71 6 1 62 23 35 18 ...` view save

user output
`50 44 66 34 82 7 37 73 39 99 9...` view save

Test 2

Verdict: ACCEPTED

input
`100 5358 5772 0 3602 6408 8742 0 848 ...` view save

correct output
`2 24 38 4 26 49 89 ...` view save

user output
`68 28 18 24 84 47 37 34 10 12 52 54 71 67 92 16 90 48 96 61 35 27 9 25 66 98 60 26 94 81 19 79 21 22 4 74 40 82 51 39 87 3 ...` view save

Test 3

Verdict: ACCEPTED

input
`100 6080 9507 0 184 7437 9307 0 3112 ...` view save

correct output
`10 23 61 4 8 9 54 85 6 ...` view save

user output
`82 68 10 4 98 53 47 83 25 15 3...` view save

Test 4

Verdict: ACCEPTED

input
`100 7910 10358 0 3180 2026 4211 0 3336 ...` view save

correct output
`6 37 12 7 28 33 24 83 2 ...` view save

user output
`74 62 68 28 88 57 56 18 58 48 30 47 29 19 87 44 16 50 6 4 37 25 38 46 42 92 8 65 85 99 72 10 100 32 54 3 63 61 23 ...` view save

Test 5

Verdict: ACCEPTED

input
`100 1065 4365 0 534 1035 4912 0 1717 ...` view save

correct output
`60 51 15 64 91 11 56 17 29 34 27 16 1 67 ...` view save

user output
`40 34 47 27 49 12 90 37 61 81 84 88 25 83 7 16 72 1 69 45 48 66 68 23 67 41 73 ...` view save

Test 6

Verdict: ACCEPTED

input
`100 5602 7097 0 1116 3686 4242 0 2388 ...` view save

correct output
`70 9 13 2 4 14 27 79 5 6 ...` view save

user output
`60 36 45 25 99 59 86 22 26 46 12 58 43 37 1 91 24 8 ...` view save

Test 7

Verdict: ACCEPTED

input
`100 735 1312 2742 5848 5964 12870 0 5587 ...` view save

correct output
`20 24 40 4 64 ...` view save

user output
`52 23 16 58 51 28 17 49 42 80 54 82 76 69 ...` view save

Test 8

Verdict: ACCEPTED

input
`100 6947 7009 3601 6490 4735 5953 0 3198 ...` view save

correct output
`72 41 6 4 8 28 25 20 ...` view save

user output
`4 62 6 10 38 16 8 36 89 95 72 7 52 84 ...` view save

Test 9

Verdict: ACCEPTED

input
`100 8177 11184 928 2996 514 4494 0 3270 ...` view save

correct output
`4 8 12 19 62 36 80 9 25 70 ...` view save

user output
`88 46 2 36 84 80 26 54 30 49 50 68 97 22 44 92 42 63 23 ...` view save

Test 10

Verdict: ACCEPTED

input
`100 6317 6616 2524 4177 1404 3977 0 2066 ...` view save

correct output
`16 10 60 38 15 34 20 18 52 5 96 9 ...` view save

user output
`40 100 71 43 92 33 5 65 80 24 54 25 48 59 58 74 64 93 41 ...` view save

Test 11

Verdict: ACCEPTED

input
`100 8329 10142 1875 3641 4458 4638 0 2442 ...` view save

correct output
`100 4 48 10 79 20 23 24 51 ...` view save

user output
`52 72 99 92 16 90 12 50 84 51 45 ...` view save

Test 12

Verdict: ACCEPTED

input
`100 806 3397 8245 10372 5982 7437 0 1107 ...` view save

correct output
`4 56 57 58 19 16 44 63 48 11 ...` view save

user output
`88 37 60 14 43 71 5 2 72 48 67 93 74 24 84 70 ...` view save

Test 13

Verdict: ACCEPTED

input
`100 8699 11259 4869 8238 8967 10472 0 2965 ...` view save

correct output
`impossible` view save

user output
`impossible` view save

Test 14

Verdict: ACCEPTED

input
`100 7759 8968 4287 8194 6041 9351 0 602 ...` view save

correct output
`68 19 24 32 12 16 ...` view save

user output
`52 30 90 65 42 12 69 62 60 83 88 56 84 53 21 22 71 ...` view save

Test 15

Verdict: ACCEPTED

input
`100 8204 10903 3919 4950 6072 7198 0 958 ...` view save

correct output
`100 91 18 36 27 15 28 10 64 46 52 50 79 ...` view save

user output
`56 16 75 57 97 39 100 10 9 22 32 69 91 99 72 46 73 62 31 80 33 70 89 41 ...` view save

Test 16

Verdict: ACCEPTED

input
`100 8522 9556 8146 10973 7621 9479 0 1728 ...` view save

correct output
`44 51 74 10 4 76 77 8 56 19 7 35 26 66 2 ...` view save

user output
`100 92 61 91 10 83 23 36 16 80 39 37 12 19 76 77 70 59 3 41 ...` view save

Test 17

Verdict: ACCEPTED

input
`100 10008 12941 7002 9420 8150 11042 0 3970 ...` view save

correct output
`4 13 22 69 43 12 15 95 20 81 77 59 1 36 62 2 34 28 5 9 ...` view save

user output
`16 76 8 85 62 11 22 53 45 17 9...` view save

Test 18

Verdict: ACCEPTED

input
`100 7356 10145 2971 5440 4831 8014 0 3699 ...` view save

correct output
`8 2 3 72 5 27 23 9 16 83 54 20 18 14 7 40 13 75 87 ...` view save

user output
`36 12 8 18 83 53 69 46 94 99 2...` view save

Test 19

Verdict: ACCEPTED

input
`100 7359 15305 5351 11786 6953 9000 0 3349 ...` view save

correct output
`8 11 16 22 24 26 28 56 2 ...` view save

user output
`72 64 74 35 57 96 27 87 8 30 37 89 95 68 55 50 48 52 34 49 10 ...` view save

Test 20

Verdict: ACCEPTED

input
`100 9267 11620 5731 9781 2532 10040 0 7355 ...` view save

correct output
`80 17 4 32 29 5 68 27 8 3 ...` view save

user output
`56 4 35 38 8 70 95 49 75 14 84 78 34 13 73 76 66 18 27 85 68 30 47 ...` view save

Test 21

Verdict: ACCEPTED

input
`100 1923 9590 1149 3602 4809 7818 0 4142 ...` view save

correct output
`36 15 16 10 44 7 76 85 72 ...` view save

user output
`36 77 30 16 9 67 89 45 12 78 85 84 55 39 76 70 14 27 ...` view save

Test 22

Verdict: ACCEPTED

input
`100 534 3023 4994 11351 2653 7810 0 4702 ...` view save

correct output
`8 17 44 64 7 72 10 12 2 ...` view save

user output
`80 92 46 10 12 98 51 69 90 4 77 27 55 36 48 21 86 96 44 73 14 ...` view save

Test 23

Verdict: ACCEPTED

input
`100 7080 13273 10948 18778 2405 7222 0 2276 ...` view save

correct output
`20 96 1 28 9 86 36 48 ...` view save

user output
`100 72 20 11 77 76 87 57 98 3 1 46 52 26 28 36 18 ...` view save

Test 24

Verdict: ACCEPTED

input
`100 16 42 66 71 38 43 0 7 ...` view save

correct output
`4 9 1 5 8 81 13 25 12 47 45 21 33 20 62 69 49 85` view save

user output
`16 84 56 80 20 60 86 30 7 59 6...` view save

Test 25

Verdict: ACCEPTED

input
`100 1 23 51 51 61 67 0 1 ...` view save

correct output
`53 65 37 4 93 9 46 24 17 69 30 33 73 89 10 35 49` view save

user output
`8 36 44 88 76 72 53 17 69 30 4...` view save

Test 26

Verdict: ACCEPTED

input
`100 2 26 16 20 21 23 0 7 ...` view save

correct output
`4 1 23 85 20 38 33 21 8 95 65 61 13 12 77 93 29 24 94 41 57 9 ...` view save

user output
`40 92 64 88 52 32 1 37 93 29 1...` view save

Test 27

Verdict: ACCEPTED

input
`100 19 47 49 53 44 50 0 2 ...` view save

correct output
`20 61 1 5 8 21 9 29 12 43 89 77 16 49 17 73 4 13 53 33 ...` view save

user output
`96 64 100 44 87 63 89 1 73 4 94 52 68 49 65 53 57 76 48 16 12 61 97 17 3 5 72 24 20 92 21 25 93 29 33 40 28 80 84 8 60 43 78 7 58 37...` view save

Test 28

Verdict: ACCEPTED

input
`100 0 26 36 44 41 41 0 2 ...` view save

correct output
`1 5 35 16 17 25 89 20 21 29 53 24 33 37 77 48 45 65 57 ...` view save

user output
`76 40 68 72 1 73 37 89 4 96 80 21 61 41 65 77 32 36 44 60 48 17 13 29 55 35 ...` view save

Test 29

Verdict: ACCEPTED

input
`100 38 59 0 4 16 23 0 10 ...` view save

correct output
`56 3 70 55 1 2 27 45 86 9 16 31 50 21 96 41 91 11 12 43 67 10 85 42 34 54 18 ...` view save

user output
`32 20 16 3 70 85 50 46 44 64 88 43 45 79 19 22 49 59 ...` view save

Test 30

Verdict: ACCEPTED

input
`100 19 37 58 68 11 18 0 4 ...` view save

correct output
`76 1 61 12 69 39 54 11 59 36 19 58 9 77 5 16 6 21 57 91 10 55 46 51 23 31 ...` view save

user output
`88 20 96 43 70 29 71 35 79 18 42 100 28 56 6 87 54 67 30 77 ...` view save

Test 31

Verdict: ACCEPTED

input
`100 50 73 29 39 35 42 0 10 ...` view save

correct output
`76 66 26 96 17 53 2 5 45 74 36 51 11 41 4 31 23 46 34 22 8 91 61 3 86 65 ...` view save

user output
`40 68 16 55 66 90 45 93 41 39 48 64 84 31 61 81 49 77 63 28 12 72 36 17 99 2 75 26 22 2...` view save

Test 32

Verdict: ACCEPTED

input
`100 14 29 8 11 7 11 0 10 ...` view save

correct output
`76 37 17 85 75 16 11 42 56 21 25 86 36 26 6 63 4 93 87 27 79 66 ...` view save

user output
`24 12 18 14 47 1 71 13 79 42 100 88 32 50 93 78 61 38 6 52 20 64 56 10 59 11 86 60 8 36 65 87 82 51 99 34 89 1...` view save

UKIEPC 2017

Knightsbridge Rises

Compiler report

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

Tasks

Submissions (Hannes Ihalainen)