Task: | Maalarit |
Sender: | comp |
Submission time: | 2016-10-09 15:54:56 +0300 |
Language: | C++ |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
#4 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.05 s | 1 | details |
#3 | WRONG ANSWER | 0.06 s | 1 | details |
#4 | WRONG ANSWER | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.06 s | 1 | details |
#7 | WRONG ANSWER | 0.05 s | 2 | details |
#8 | WRONG ANSWER | 0.06 s | 2 | details |
#9 | WRONG ANSWER | 0.05 s | 2 | details |
#10 | ACCEPTED | 0.06 s | 2 | details |
#11 | WRONG ANSWER | 0.06 s | 2 | details |
#12 | ACCEPTED | 0.06 s | 2 | details |
#13 | WRONG ANSWER | 0.05 s | 3 | details |
#14 | WRONG ANSWER | 0.05 s | 3 | details |
#15 | WRONG ANSWER | 0.05 s | 3 | details |
#16 | WRONG ANSWER | 0.06 s | 3 | details |
#17 | WRONG ANSWER | 0.05 s | 3 | details |
#18 | ACCEPTED | 0.06 s | 3 | details |
#19 | TIME LIMIT EXCEEDED | -- | 4 | details |
#20 | TIME LIMIT EXCEEDED | -- | 4 | details |
#21 | TIME LIMIT EXCEEDED | -- | 4 | details |
#22 | TIME LIMIT EXCEEDED | -- | 4 | details |
#23 | TIME LIMIT EXCEEDED | -- | 4 | details |
#24 | RUNTIME ERROR | 1.62 s | 4 | details |
Code
#include <iostream>#include <vector>#include <map>int number_of_boards;typedef struct {std::map<int, int> board_painters;int cost_one;int cost_two;int cost_three;} data;int sum(data data) {return data.cost_one + data.cost_two + data.cost_three;}data painters_for_two(std::pair<int, int> board_one, std::pair<int, int> board_two, data data) {int board_one_location = board_one.first;int board_two_location = board_two.first;int board_one_height = board_one.second;int board_two_height = board_two.second;if (board_one.second >= board_two.second) {data.board_painters.insert(std::pair<int, int>(board_one_location, 2));data.board_painters.insert(std::pair<int, int>(board_two_location, 1));if (board_one_height > data.cost_two) {data.cost_two = board_one_height;}if (board_two_height > data.cost_one) {data.cost_one = board_two_height;}} else {data.board_painters.insert(std::pair<int, int>(board_one_location, 1));data.board_painters.insert(std::pair<int, int>(board_two_location, 2));if (board_one_height > data.cost_one) {data.cost_one = board_one_height;}if (board_two_height > data.cost_two) {data.cost_two = board_two_height;}}return data;}data two_painter_sequence(std::map<int, int> boards, bool is_bottom, data d) {int painter = 2;if (is_bottom == true && boards.size() % 2 == 0) {painter = 3;}for(auto board: boards) {d.board_painters.insert(std::pair<int, int>(board.first, painter));if (painter == 2) {if (board.second > d.cost_two) {d.cost_two = board.second;}painter = 3;} else {if (board.second > d.cost_three) {d.cost_three= board.second;}painter = 2;}}return d;}data find_painters(std::map<int, int> boards, bool is_bottom, data d) {std::pair<int, int> tallestBoard = std::pair<int, int>(boards.rbegin()->first, boards.rbegin()->second);std::vector<std::pair<int, int>> options = {tallestBoard};for(auto board: boards) {if (board.second > tallestBoard.second) {tallestBoard = board;options.clear();options.push_back(board);} else if (board.second == tallestBoard.second && board.first != tallestBoard.first) {options.push_back(board);}}std::vector<data> possible_datas;for(auto option: options) {data possible_data = d;int tallestLocation = option.first;int tallestHeight = option.second;if ((tallestLocation == boards.begin()->first || tallestLocation == boards.rbegin()->first) && boards.rbegin()->first != number_of_boards && boards.begin()->first != 1) {std::map<int, int> boards_subset = boards;boards_subset.erase(boards.begin()->first);boards_subset.erase(boards.rbegin()->first);option = std::pair<int, int>(boards_subset.rbegin()->first, boards_subset.rbegin()->second);for(auto board: boards_subset) {if (board.second > option.second) {option = board;}}tallestLocation = option.first;tallestHeight = option.second;} else if (tallestLocation == boards.begin()->first && is_bottom == false) {std::map<int, int> boards_subset = boards;boards_subset.erase(boards.begin()->first);option = std::pair<int, int>(boards_subset.rbegin()->first, boards_subset.rbegin()->second);for(auto board: boards_subset) {if (board.second > option.second) {option = board;}}tallestLocation = option.first;tallestHeight = option.second;} else if (tallestLocation == boards.rbegin()->first && is_bottom == true) {std::map<int, int> boards_subset = boards;boards_subset.erase(boards.rbegin()->first);option = std::pair<int, int>(boards_subset.rbegin()->first, boards_subset.rbegin()->second);for(auto board: boards_subset) {if (board.second > option.second) {option = board;}}tallestLocation = option.first;tallestHeight = option.second;}possible_data.board_painters.insert(std::pair<int, int>(tallestLocation, 3));if (tallestHeight > possible_data.cost_three) {possible_data.cost_three = tallestHeight;}std::map<int, int> board_set_bottom;std::map<int, int> board_set_top;for(auto board: boards) {if (board.first < tallestLocation) {board_set_bottom.insert(std::pair<int, int>(board.first, board.second));} else if (board.first > tallestLocation) {board_set_top.insert(std::pair<int, int>(board.first, board.second));}}if (board_set_top.size() > 1 && board_set_top.rbegin()->first == number_of_boards) {possible_data = find_painters(board_set_top, false, possible_data);board_set_top.clear();} else if (board_set_bottom.size() > 1 && board_set_bottom.begin()->first == 1) {possible_data = find_painters(board_set_bottom, true, possible_data);board_set_bottom.clear();}int bottom_size = board_set_bottom.size();int top_size = board_set_top.size();if (board_set_bottom.empty() == false) {if (bottom_size > 2) {possible_data = find_painters(board_set_bottom, true, possible_data);} else if (bottom_size == 2) {std::pair<int, int> board_one = std::pair<int, int>(board_set_bottom.begin()->first, board_set_bottom.begin()->second);std::pair<int, int> board_two = std::pair<int, int>(board_set_bottom.rbegin()->first, board_set_bottom.rbegin()->second);possible_data = painters_for_two(board_one, board_two, possible_data);} else if (bottom_size == 1) {std::pair<int, int> board = std::pair<int, int>(board_set_bottom.begin()->first, board_set_bottom.begin()->second);possible_data.board_painters.insert(std::pair<int, int>(board.first, 2));if (board.second > possible_data.cost_two) {possible_data.cost_two = board.second;}}}if (board_set_top.empty() == false) {if (top_size > 2) {possible_data = find_painters(board_set_top, false, possible_data);} else if (top_size == 2) {std::pair<int, int> board_one = std::pair<int, int>(board_set_top.begin()->first, board_set_top.begin()->second);std::pair<int, int> board_two = std::pair<int, int>(board_set_top.rbegin()->first, board_set_top.rbegin()->second);possible_data = painters_for_two(board_one, board_two, possible_data);} else if (top_size == 1) {std::pair<int, int> board = std::pair<int, int>(board_set_top.begin()->first, board_set_top.begin()->second);possible_data.board_painters.insert(std::pair<int, int>(board.first, 2));if (board.second > possible_data.cost_two) {possible_data.cost_two = board.second;}}}possible_datas.push_back(possible_data);}possible_datas.push_back(two_painter_sequence(boards, is_bottom, d));data best_data = possible_datas.front();for(auto data: possible_datas) {if (sum(data) < sum(best_data)) {best_data = data;}}return best_data;}data find_first_painter(std::map<int, int> boards) {data d;d.cost_one = 0;d.cost_two = 0;d.cost_three = 0;if (boards.size() == 1) {std::pair<int, int> board = std::pair<int, int>(boards.begin()->first, boards.begin()->second);d.cost_one = board.second;d.board_painters.insert(std::pair<int, int>(board.first, 1));return d;} else if (boards.size() == 2) {std::pair<int, int> board_one = std::pair<int, int>(boards.begin()->first, boards.begin()->second);std::pair<int, int> board_two = std::pair<int, int>(boards.rbegin()->first, boards.rbegin()->second);d.cost_one = board_one.second;d.cost_two = board_two.second;d.board_painters.insert(std::pair<int, int>(board_one.first, 1));d.board_painters.insert(std::pair<int, int>(board_two.first, 2));return d;}std::pair<int, int> tallestBoard = std::pair<int, int>(boards.rbegin()->first, boards.rbegin()->second);std::vector<std::pair<int, int>> options = {tallestBoard};for(auto board: boards) {if (board.second > tallestBoard.second) {tallestBoard = board;options.clear();options.push_back(board);} else if (board.second == tallestBoard.second && board.first != tallestBoard.first) {options.push_back(board);}}std::vector<data> possible_datas;for(auto option: options) {data possible_data = d;int tallestLocation = option.first;int tallestHeight = option.second;possible_data.board_painters.insert(std::pair<int, int>(tallestLocation, 3));possible_data.cost_three = tallestHeight;std::map<int, int> board_set_bottom;std::map<int, int> board_set_top;for(auto board: boards) {if (board.first < tallestLocation) {board_set_bottom.insert(std::pair<int, int>(board.first, board.second));} else if (board.first > tallestLocation) {board_set_top.insert(std::pair<int, int>(board.first, board.second));}}std::vector<std::map<int, int>> board_sets;board_sets.push_back(board_set_bottom);board_sets.push_back(board_set_top);for(auto board_set: board_sets) {int set_size = board_set.size();if (set_size == 0) {continue;}if (set_size > 2) {if (board_set == board_set_bottom) {std::map<int, int> bottom_set_copy = board_set_bottom;board_set_bottom = bottom_set_copy;possible_data = find_painters(board_set, true, possible_data);} else {possible_data = find_painters(board_set, false, possible_data);}} else if (board_set.rbegin()->first == number_of_boards && board_set == board_set_top && set_size != 1) {possible_data = find_painters(board_set, false, possible_data);} else if (board_set.begin()->first == 1 && board_set == board_set_bottom && set_size != 1) {possible_data = find_painters(board_set, true, possible_data);} else if (set_size == 1) {std::pair<int, int> board = *(board_set.rbegin());possible_data.board_painters.insert(std::pair<int, int>(board.first, 2));if (board.second > possible_data.cost_two) {possible_data.cost_two = board.second;}}}possible_datas.push_back(possible_data);}data best_data = possible_datas.front();for(auto data: possible_datas) {if (sum(data) < sum(best_data)) {best_data = data;}}return best_data;}int main() {std::cin >> number_of_boards;std::map<int, int> boards;int x;for(int p = 1; p <= number_of_boards; ++p) {std::cin >> x;boards.insert(std::pair<int, int>(p, x)); // location, height}data data = find_first_painter(boards);int costs[3] = {data.cost_one, data.cost_two, data.cost_three};std::map<int, int> board_painters = data.board_painters;int number_of_painters = 0;for(auto cost: costs) {if (cost != 0) {number_of_painters += 1;}}int lowest_painter = 3;for(auto set: board_painters) {if (set.second < lowest_painter) {lowest_painter = set.second;}}if (lowest_painter != 1) {for(auto set: board_painters) {std::pair<int, int> new_set = std::pair<int, int>(set.first, set.second - lowest_painter + 1);board_painters.erase(set.first);board_painters.insert(new_set);}}if (number_of_painters == 3) {int first_digit = board_painters.at(1);int second_digit = board_painters.at(2);for(auto set: board_painters) {int value = set.second;std::pair<int, int> new_set;if (value == first_digit) {new_set = std::pair<int, int>(set.first, 1);} else if (value == second_digit) {new_set = std::pair<int, int>(set.first, 2);} else {new_set = std::pair<int, int>(set.first, 3);}board_painters.erase(set.first);board_painters.insert(new_set);}} else if (number_of_painters == 2) {if (board_painters.at(1) != 1) {for(auto set: board_painters) {std::pair<int, int> new_set;if (set.second == 1) {new_set = std::pair<int, int>(set.first, 2);} else {new_set = std::pair<int, int>(set.first, 1);}board_painters.erase(set.first);board_painters.insert(new_set);}}}std::cout << sum(data) << " " << number_of_painters << "\n";std::map<int, int> print_set = board_painters;print_set.erase(print_set.rbegin()->first);for(auto set: print_set) {std::cout << set.second << " ";}std::cout << board_painters.rbegin()->second;return 0;}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
10 22 54 3 91 69 90 40 29 83 71 |
correct output |
---|
174 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
174 2 1 2 1 2 1 2 1 2 1 2 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
10 49 3 96 38 90 18 92 74 83 1 |
correct output |
---|
170 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
170 2 1 2 1 2 1 2 1 2 1 2 |
Test 3
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 46 3 41 30 16 17 12 93 80 81 |
correct output |
---|
173 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
173 2 1 2 1 2 1 2 1 1 2 1 |
Test 4
Group: 1
Verdict: WRONG ANSWER
input |
---|
10 46 8 95 85 82 73 82 92 53 90 |
correct output |
---|
187 3 1 2 1 2 1 2 1 2 1 2 |
user output |
---|
177 2 1 2 1 1 2 1 2 1 2 1 |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
10 41 18 61 59 40 96 5 2 74 38 |
correct output |
---|
159 3 2 1 2 1 2 1 2 3 1 2 |
user output |
---|
159 3 1 2 1 2 1 2 1 3 2 1 |
Test 6
Group: 1
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 7
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 1 39 94 5 24 84 84 10 78 61 38... |
correct output |
---|
193 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
188 2 1 2 1 2 1 2 1 2 1 2 1 1 2 1 2 ... |
Test 8
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 31 73 18 88 49 28 66 5 32 48 9... |
correct output |
---|
199 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
179 2 1 2 1 2 1 2 1 2 1 2 2 1 2 1 2 ... |
Test 9
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 45 56 36 60 31 10 23 79 29 17 ... |
correct output |
---|
198 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
194 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
100 1 77 70 62 21 68 40 54 90 62 1... |
correct output |
---|
194 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
194 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 11
Group: 2
Verdict: WRONG ANSWER
input |
---|
100 4 47 41 81 56 64 12 10 20 100 ... |
correct output |
---|
189 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
186 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 ... |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 13
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 256160448 813097800 167146270 ... |
correct output |
---|
1929869257 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
-2020397592 3 1 2 1 2 1 2 1 3 2 1 3 2 1 3 2 ... |
Test 14
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 520002672 3542567 24668528 959... |
correct output |
---|
1946957555 3 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-1889752545 3 1 2 3 1 3 2 1 1 3 1 3 1 2 3 1 ... |
Test 15
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 483158423 780224665 844754665 ... |
correct output |
---|
1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-2036855897 3 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 ... |
Test 16
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 969647264 128558017 889036329 ... |
correct output |
---|
1997942264 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
-1846966078 3 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 ... |
Test 17
Group: 3
Verdict: WRONG ANSWER
input |
---|
100 745018527 400495893 635468795 ... |
correct output |
---|
1961391143 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
1894358879 3 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 ... |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
10 1 1 1 1 1 1 1 1 1 1 |
correct output |
---|
2 3 2 1 2 1 2 1 2 1 2 1 |
user output |
---|
2 2 1 2 1 2 1 2 1 2 1 2 |
Test 19
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 197349274 775463806 263930657 ... |
correct output |
---|
1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 20
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 102296405 34648120 320393597 9... |
correct output |
---|
1999930943 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
user output |
---|
(empty) |
Test 21
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 781254921 418252056 502363453 ... |
correct output |
---|
1999987794 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 22
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 849784881 230439009 455097426 ... |
correct output |
---|
1999979439 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 23
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 851456132 13422224 537539701 4... |
correct output |
---|
1999948226 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
user output |
---|
(empty) |
Test 24
Group: 4
Verdict: RUNTIME ERROR
input |
---|
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
2 3 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ... |
user output |
---|
(empty) |