#include <algorithm> #include <iostream> #include <limits> #include <utility> #include <vector> void another_day(std::vector<char>& cities) { for (int i = 0; i < cities.size() - 1; i++) { if (cities[i] == '0' && cities[i + 1] == '1') { cities[i] = '1'; } if (cities[i] == '1' && cities[i + 1] == '0') { cities[i + 1] = '1'; i++; } } } bool is_pandemic_stable(const std::vector<char>& cities) { for (int i = 0; i < cities.size() - 1; i++) { if (cities[i] == '1' && cities[i + 1] == '0') { return false; } if (cities[i] == '0' && cities[i + 1] == '1') { return false; } } return true; } void vaccinate(std::vector<char>& cities, int id) { cities[id] = '2'; } std::pair<int, int> find_border_city(const std::vector<char>& cities) { std::vector<int> sequences(cities.size()); int max_sequence{std::numeric_limits<int>::min()}; int max_id{0}; int max2_sequence{std::numeric_limits<int>::min()}; int max2_id{0}; bool is_2_started{false}; for (int i = 0; i < cities.size(); ++i) { if (i == 0 && cities[i] == '0') { sequences[i] = 1; } else if (cities[i] == '0') { sequences[i] = sequences[i - 1] + 1; } else if (cities[i] == '2' && is_2_started) { sequences[i] = 0; max2_sequence = -1; max2_id = -1; is_2_started = false; } else if (cities[i] == '2') { sequences[i] = 0; is_2_started = true; } else { sequences[i] = 0; } if (!is_2_started && sequences[i] > max_sequence) { max_sequence = sequences[i]; max_id = i; } if (is_2_started && sequences[i] > max2_sequence) { max2_sequence = sequences[i]; max2_id = i; } } if (max_sequence > max2_sequence) { return std::make_pair(max_id - (max_sequence - 1), max_id); } return std::make_pair(max2_id - (max2_sequence - 1), max2_id); } int pan(std::vector<char> cities) { // O(N) while (!is_pandemic_stable(cities)) { // O(N) const auto& [start_id, stop_id] = find_border_city(cities); int vaccination_id = 0; if (start_id == 0) { vaccination_id = stop_id; } else if (stop_id == cities.size() - 1) { vaccination_id = start_id; } else if (cities[start_id - 1] == '1') { vaccination_id = start_id; } else { vaccination_id = stop_id; } vaccinate(cities, vaccination_id); // O(N) another_day(cities); } // O(N) return std::count(cities.cbegin(), cities.cend(), '1'); } int main() { int test_cases{}; std::cin >> test_cases; for (int i = 0; i < test_cases; ++i) { int cities_count{}; std::cin >> cities_count; std::vector<char> cities(cities_count); for (int i = 0; i < cities_count; ++i) { std::cin >> cities[i]; } std::cout << pan(cities) << "\n"; } return 0; }
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <algorithm> #include <iostream> #include <limits> #include <utility> #include <vector> void another_day(std::vector<char>& cities) { for (int i = 0; i < cities.size() - 1; i++) { if (cities[i] == '0' && cities[i + 1] == '1') { cities[i] = '1'; } if (cities[i] == '1' && cities[i + 1] == '0') { cities[i + 1] = '1'; i++; } } } bool is_pandemic_stable(const std::vector<char>& cities) { for (int i = 0; i < cities.size() - 1; i++) { if (cities[i] == '1' && cities[i + 1] == '0') { return false; } if (cities[i] == '0' && cities[i + 1] == '1') { return false; } } return true; } void vaccinate(std::vector<char>& cities, int id) { cities[id] = '2'; } std::pair<int, int> find_border_city(const std::vector<char>& cities) { std::vector<int> sequences(cities.size()); int max_sequence{std::numeric_limits<int>::min()}; int max_id{0}; int max2_sequence{std::numeric_limits<int>::min()}; int max2_id{0}; bool is_2_started{false}; for (int i = 0; i < cities.size(); ++i) { if (i == 0 && cities[i] == '0') { sequences[i] = 1; } else if (cities[i] == '0') { sequences[i] = sequences[i - 1] + 1; } else if (cities[i] == '2' && is_2_started) { sequences[i] = 0; max2_sequence = -1; max2_id = -1; is_2_started = false; } else if (cities[i] == '2') { sequences[i] = 0; is_2_started = true; } else { sequences[i] = 0; } if (!is_2_started && sequences[i] > max_sequence) { max_sequence = sequences[i]; max_id = i; } if (is_2_started && sequences[i] > max2_sequence) { max2_sequence = sequences[i]; max2_id = i; } } if (max_sequence > max2_sequence) { return std::make_pair(max_id - (max_sequence - 1), max_id); } return std::make_pair(max2_id - (max2_sequence - 1), max2_id); } int pan(std::vector<char> cities) { // O(N) while (!is_pandemic_stable(cities)) { // O(N) const auto& [start_id, stop_id] = find_border_city(cities); int vaccination_id = 0; if (start_id == 0) { vaccination_id = stop_id; } else if (stop_id == cities.size() - 1) { vaccination_id = start_id; } else if (cities[start_id - 1] == '1') { vaccination_id = start_id; } else { vaccination_id = stop_id; } vaccinate(cities, vaccination_id); // O(N) another_day(cities); } // O(N) return std::count(cities.cbegin(), cities.cend(), '1'); } int main() { int test_cases{}; std::cin >> test_cases; for (int i = 0; i < test_cases; ++i) { int cities_count{}; std::cin >> cities_count; std::vector<char> cities(cities_count); for (int i = 0; i < cities_count; ++i) { std::cin >> cities[i]; } std::cout << pan(cities) << "\n"; } return 0; } |