#include <cstdio> #include <vector> long long int result = 0; struct { int queue_[4000005]; int first_, last_; int translation_; void Translate(int x) { translation_ += x; } void Add(int x) { x -= translation_; while (last_ > first_ and queue_[last_ - 1] > x) { last_--; } queue_[last_++] = x; } void Remove(int x) { x -= translation_; if (first_ < last_ and queue_[first_] == x) { first_++; } } int Min() { return queue_[first_] + translation_; } void Clear() { translation_ = first_ = last_ = 0; } } monotonous_queue; struct { std::vector<int> things_[8 * 1000005]; int translation_; void Clear() { translation_ = -4 * 1000005; } void Translate(int x) { translation_ += x; } std::vector<int>& Get(int x) { x -= translation_; return things_[x]; } } translated_table; int n, m; int money[2000005]; char game_results[2000005]; bool result_is_assigned[2000005]; int d; int person[4000005]; int points[4000005]; int results[4000005]; long long int death[4000005]; int reverse_lookup[4000005]; void Sweeps() { translated_table.Clear(); for (int i = 0; i < 2 * d; i++) { if (person[i] != -1) { translated_table.Get(points[i]).push_back(person[i]); reverse_lookup[person[i]] = i; } translated_table.Translate(results[i]); for (int p : translated_table.Get(0)) { death[p] += i - reverse_lookup[p] + 1; } translated_table.Get(0).clear(); } } void Drops() { for (int i = 0; i < d; i++) { person[d + i] = -1; results[d + i] = results[i]; } monotonous_queue.Clear(); int sum = 0; for (int i = 0; i < d; i++) { sum += results[i]; monotonous_queue.Add(sum); } for (int i = 0; i < d; i++) { if (person[i] != -1) { if (points[i] + monotonous_queue.Min() > 0 and sum < 0) { int k = (monotonous_queue.Min() + points[i]) / -sum; for (int j = 0; j < 2; j++) { if (points[i] + monotonous_queue.Min() + sum * (k + j) <= 0) { break; } k++; } death[person[i]] += (long long int) k * d; points[i] += sum * k; } } monotonous_queue.Remove(results[i]); monotonous_queue.Translate(-results[i]); sum -= results[i]; sum += results[d + i]; monotonous_queue.Add(sum); } } void RunsCycle() { Drops(); Sweeps(); for (int i = 0; i < d; i++) { if (person[i] != -1) { if (death[person[i]]) { long long int time = death[person[i]] - 1; time *= n; time += person[i] + 1; if (result == 0ll or result > time) { result = time; } } } } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &money[i]); } scanf("%d%s", &m, game_results); while (m < n) { for (int i = 0; i < m; i++) { game_results[m + i] = game_results[i]; } m *= 2; } for (int i = 0; i < m; i++) { if (not result_is_assigned[i]) { d = 0; int position = i; do { result_is_assigned[position] = true; results[d] = (game_results[position] == 'W') ? 1 : -1; if (position < n) { person[d] = position; points[d] = money[position]; } else { person[d] = -1; } d++; position = (position + n) % m; } while (position != i); RunsCycle(); } } if (result == 0ll) { printf("-1\n"); } else { printf("%lld\n", result); } 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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | #include <cstdio> #include <vector> long long int result = 0; struct { int queue_[4000005]; int first_, last_; int translation_; void Translate(int x) { translation_ += x; } void Add(int x) { x -= translation_; while (last_ > first_ and queue_[last_ - 1] > x) { last_--; } queue_[last_++] = x; } void Remove(int x) { x -= translation_; if (first_ < last_ and queue_[first_] == x) { first_++; } } int Min() { return queue_[first_] + translation_; } void Clear() { translation_ = first_ = last_ = 0; } } monotonous_queue; struct { std::vector<int> things_[8 * 1000005]; int translation_; void Clear() { translation_ = -4 * 1000005; } void Translate(int x) { translation_ += x; } std::vector<int>& Get(int x) { x -= translation_; return things_[x]; } } translated_table; int n, m; int money[2000005]; char game_results[2000005]; bool result_is_assigned[2000005]; int d; int person[4000005]; int points[4000005]; int results[4000005]; long long int death[4000005]; int reverse_lookup[4000005]; void Sweeps() { translated_table.Clear(); for (int i = 0; i < 2 * d; i++) { if (person[i] != -1) { translated_table.Get(points[i]).push_back(person[i]); reverse_lookup[person[i]] = i; } translated_table.Translate(results[i]); for (int p : translated_table.Get(0)) { death[p] += i - reverse_lookup[p] + 1; } translated_table.Get(0).clear(); } } void Drops() { for (int i = 0; i < d; i++) { person[d + i] = -1; results[d + i] = results[i]; } monotonous_queue.Clear(); int sum = 0; for (int i = 0; i < d; i++) { sum += results[i]; monotonous_queue.Add(sum); } for (int i = 0; i < d; i++) { if (person[i] != -1) { if (points[i] + monotonous_queue.Min() > 0 and sum < 0) { int k = (monotonous_queue.Min() + points[i]) / -sum; for (int j = 0; j < 2; j++) { if (points[i] + monotonous_queue.Min() + sum * (k + j) <= 0) { break; } k++; } death[person[i]] += (long long int) k * d; points[i] += sum * k; } } monotonous_queue.Remove(results[i]); monotonous_queue.Translate(-results[i]); sum -= results[i]; sum += results[d + i]; monotonous_queue.Add(sum); } } void RunsCycle() { Drops(); Sweeps(); for (int i = 0; i < d; i++) { if (person[i] != -1) { if (death[person[i]]) { long long int time = death[person[i]] - 1; time *= n; time += person[i] + 1; if (result == 0ll or result > time) { result = time; } } } } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &money[i]); } scanf("%d%s", &m, game_results); while (m < n) { for (int i = 0; i < m; i++) { game_results[m + i] = game_results[i]; } m *= 2; } for (int i = 0; i < m; i++) { if (not result_is_assigned[i]) { d = 0; int position = i; do { result_is_assigned[position] = true; results[d] = (game_results[position] == 'W') ? 1 : -1; if (position < n) { person[d] = position; points[d] = money[position]; } else { person[d] = -1; } d++; position = (position + n) % m; } while (position != i); RunsCycle(); } } if (result == 0ll) { printf("-1\n"); } else { printf("%lld\n", result); } return 0; } |