#include <iostream> #include <cstdint> #include <vector> #include <map> uint32_t bottles[50000]; void swap(uint32_t& a, uint32_t& b) { uint32_t temp = a; a = b; b = temp; } bool check_input(const uint32_t bottles_amount, const uint32_t required_different_types_amount) { std::map<uint32_t, uint32_t> numbers_occurences; for (uint32_t i = 0; i < bottles_amount; i++) { uint32_t& occurences_amount = numbers_occurences[bottles[i]]; occurences_amount++; } if (numbers_occurences.size() < required_different_types_amount) return false; for (std::pair<uint32_t, uint32_t> number_occurences : numbers_occurences) { if (number_occurences.second >= required_different_types_amount) return true; } return false; } int main() { uint32_t bottles_amount, required_different_types_amount; std::cin >> bottles_amount >> required_different_types_amount; for (uint32_t i = 0; i < bottles_amount; i++) std::cin >> bottles[i]; if (check_input(bottles_amount, required_different_types_amount) == false) { std::cout << -1; return 0; } uint32_t required_moves = 0; std::map<uint32_t, bool> first_bottles = { { bottles[0], true } }; for (uint32_t i = 1; i < required_different_types_amount; i++) { if (first_bottles[bottles[i]] == true) { uint32_t target_index = -1; uint32_t target_number = -1; for (uint32_t x = i + 1; x < bottles_amount; x++) { if (bottles[x] != bottles[i]) { target_index = x; target_number = bottles[x]; break; } } if (target_index == -1) { std::cout << -1; return 0; } for (uint32_t x = target_index; x > i; x--) { swap(bottles[x], bottles[x - 1]); } first_bottles.insert({ target_number, true }); required_moves += target_index - i; } else { first_bottles.insert({ bottles[i], true }); } } std::cout << required_moves; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #include <iostream> #include <cstdint> #include <vector> #include <map> uint32_t bottles[50000]; void swap(uint32_t& a, uint32_t& b) { uint32_t temp = a; a = b; b = temp; } bool check_input(const uint32_t bottles_amount, const uint32_t required_different_types_amount) { std::map<uint32_t, uint32_t> numbers_occurences; for (uint32_t i = 0; i < bottles_amount; i++) { uint32_t& occurences_amount = numbers_occurences[bottles[i]]; occurences_amount++; } if (numbers_occurences.size() < required_different_types_amount) return false; for (std::pair<uint32_t, uint32_t> number_occurences : numbers_occurences) { if (number_occurences.second >= required_different_types_amount) return true; } return false; } int main() { uint32_t bottles_amount, required_different_types_amount; std::cin >> bottles_amount >> required_different_types_amount; for (uint32_t i = 0; i < bottles_amount; i++) std::cin >> bottles[i]; if (check_input(bottles_amount, required_different_types_amount) == false) { std::cout << -1; return 0; } uint32_t required_moves = 0; std::map<uint32_t, bool> first_bottles = { { bottles[0], true } }; for (uint32_t i = 1; i < required_different_types_amount; i++) { if (first_bottles[bottles[i]] == true) { uint32_t target_index = -1; uint32_t target_number = -1; for (uint32_t x = i + 1; x < bottles_amount; x++) { if (bottles[x] != bottles[i]) { target_index = x; target_number = bottles[x]; break; } } if (target_index == -1) { std::cout << -1; return 0; } for (uint32_t x = target_index; x > i; x--) { swap(bottles[x], bottles[x - 1]); } first_bottles.insert({ target_number, true }); required_moves += target_index - i; } else { first_bottles.insert({ bottles[i], true }); } } std::cout << required_moves; } |