#include <bits/stdc++.h> using namespace std; int FirstGeq(const vector<int>& tree, int a, int lt, int rt, int l, int r, int value) { if (l > rt or r < lt) return -1; if (l <= lt and r >= rt) { if (tree[a] < value) return -1; int width = rt - lt + 1; while (width > 1) { if (tree[2 * a] >= value) a = 2 * a; else a = 2 * a + 1; width /= 2; } return a; } int mid = (lt + rt) / 2; int left = FirstGeq(tree, 2 * a, lt, mid, l, r, value); if (left != -1) return left; else return FirstGeq(tree, 2 * a + 1, mid + 1, rt, l, r, value); } int Max(const vector<int>& tree, int l, int r) { int T = tree.size() / 2; l += T; r += T; int res = max(tree[l], tree[r]); while (l/2 != r/2) { if (l % 2 == 0) res = max(res, tree[l + 1]); if (r % 2 == 1) res = max(res, tree[r - 1]); l /= 2; r /= 2; } return res; } int main() { int n; cin >> n; vector<int> budget(n); for (int i = 0; i < n; ++i) cin >> budget[i]; int m; cin >> m; string machine; cin >> machine; assert(machine.length() == m); vector<vector<int>> cycles; vector<int> cycle_number(m, -1), pos_in_cycle(m); for (int i = 0; i < m; ++i) { if (cycle_number[i] != -1) continue; int new_cycle_number = cycles.size(); cycles.push_back(vector<int>()); vector<int>& cycle = cycles.back(); int j = i, pos = 0; do { cycle_number[j] = new_cycle_number; pos_in_cycle[j] = pos; cycle.push_back(j); pos++; j = (j + n) % m; } while (j != i); assert(cycle.size() == cycles[0].size()); } assert(cycles[0].size() * cycles.size() == m); int cycle_length = cycles[0].size(); int T = 1; while (T < cycle_length + 1) T *= 2; vector<vector<int>> trees(cycles.size(), vector<int>(2 * T)); for (int i = 0; i < cycles.size(); ++i) { for (int j = 0; j < cycle_length; ++j) trees[i][T + j + 1] = trees[i][T + j] + (machine[cycles[i][j]] == 'P' ? 1 : -1); for (int j = T - 1; j > 0; --j) trees[i][j] = max(trees[i][2 * j], trees[i][2 * j + 1]); } vector<long long> solutions; for (int i = 0; i < n; ++i) { int start_pos = i % m; int cycle_outcome = trees[cycle_number[start_pos]][T + cycle_length]; const vector<int>& tree = trees[cycle_number[start_pos]]; int pic = pos_in_cycle[start_pos]; int max_loss = max( Max(tree, pic, cycle_length) - tree[T + pic], Max(tree, 0, pic) + tree[T + cycle_length] - tree[T + pic]); if (cycle_outcome <= 0 and max_loss < budget[i]) continue; int full_cycles_before_bankrupcy = budget[i] > max_loss ? (budget[i] - max_loss + cycle_outcome - 1) / cycle_outcome : 0; // cerr << "i = " << " budget = " << budget[i] << " max_loss = " << max_loss << " cycles_before_bankrupcy = " << full_cycles_before_bankrupcy << endl; int rest = budget[i] - cycle_outcome * full_cycles_before_bankrupcy; int which_turn = 0; int temp = FirstGeq(tree, 1, 0, T-1, pic, cycle_length, rest + tree[T + pic]); if (temp == -1) { which_turn = cycle_length - pic; temp = FirstGeq(tree, 1, 0, T-1, 0, pic, rest - (tree[T + cycle_length] - tree[T + pic])); assert(temp != -1); which_turn += temp - T; } else { which_turn = temp - T - pic; } // cerr << "which_turn = " << which_turn << endl; solutions.push_back(1 + i + (full_cycles_before_bankrupcy * (long long)cycle_length + which_turn - 1) * n); // cerr << i << " " << solutions.back() << endl; } if (solutions.empty()) cout << -1 << endl; else cout << *min_element(solutions.begin(), solutions.end()) << endl; }
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 | #include <bits/stdc++.h> using namespace std; int FirstGeq(const vector<int>& tree, int a, int lt, int rt, int l, int r, int value) { if (l > rt or r < lt) return -1; if (l <= lt and r >= rt) { if (tree[a] < value) return -1; int width = rt - lt + 1; while (width > 1) { if (tree[2 * a] >= value) a = 2 * a; else a = 2 * a + 1; width /= 2; } return a; } int mid = (lt + rt) / 2; int left = FirstGeq(tree, 2 * a, lt, mid, l, r, value); if (left != -1) return left; else return FirstGeq(tree, 2 * a + 1, mid + 1, rt, l, r, value); } int Max(const vector<int>& tree, int l, int r) { int T = tree.size() / 2; l += T; r += T; int res = max(tree[l], tree[r]); while (l/2 != r/2) { if (l % 2 == 0) res = max(res, tree[l + 1]); if (r % 2 == 1) res = max(res, tree[r - 1]); l /= 2; r /= 2; } return res; } int main() { int n; cin >> n; vector<int> budget(n); for (int i = 0; i < n; ++i) cin >> budget[i]; int m; cin >> m; string machine; cin >> machine; assert(machine.length() == m); vector<vector<int>> cycles; vector<int> cycle_number(m, -1), pos_in_cycle(m); for (int i = 0; i < m; ++i) { if (cycle_number[i] != -1) continue; int new_cycle_number = cycles.size(); cycles.push_back(vector<int>()); vector<int>& cycle = cycles.back(); int j = i, pos = 0; do { cycle_number[j] = new_cycle_number; pos_in_cycle[j] = pos; cycle.push_back(j); pos++; j = (j + n) % m; } while (j != i); assert(cycle.size() == cycles[0].size()); } assert(cycles[0].size() * cycles.size() == m); int cycle_length = cycles[0].size(); int T = 1; while (T < cycle_length + 1) T *= 2; vector<vector<int>> trees(cycles.size(), vector<int>(2 * T)); for (int i = 0; i < cycles.size(); ++i) { for (int j = 0; j < cycle_length; ++j) trees[i][T + j + 1] = trees[i][T + j] + (machine[cycles[i][j]] == 'P' ? 1 : -1); for (int j = T - 1; j > 0; --j) trees[i][j] = max(trees[i][2 * j], trees[i][2 * j + 1]); } vector<long long> solutions; for (int i = 0; i < n; ++i) { int start_pos = i % m; int cycle_outcome = trees[cycle_number[start_pos]][T + cycle_length]; const vector<int>& tree = trees[cycle_number[start_pos]]; int pic = pos_in_cycle[start_pos]; int max_loss = max( Max(tree, pic, cycle_length) - tree[T + pic], Max(tree, 0, pic) + tree[T + cycle_length] - tree[T + pic]); if (cycle_outcome <= 0 and max_loss < budget[i]) continue; int full_cycles_before_bankrupcy = budget[i] > max_loss ? (budget[i] - max_loss + cycle_outcome - 1) / cycle_outcome : 0; // cerr << "i = " << " budget = " << budget[i] << " max_loss = " << max_loss << " cycles_before_bankrupcy = " << full_cycles_before_bankrupcy << endl; int rest = budget[i] - cycle_outcome * full_cycles_before_bankrupcy; int which_turn = 0; int temp = FirstGeq(tree, 1, 0, T-1, pic, cycle_length, rest + tree[T + pic]); if (temp == -1) { which_turn = cycle_length - pic; temp = FirstGeq(tree, 1, 0, T-1, 0, pic, rest - (tree[T + cycle_length] - tree[T + pic])); assert(temp != -1); which_turn += temp - T; } else { which_turn = temp - T - pic; } // cerr << "which_turn = " << which_turn << endl; solutions.push_back(1 + i + (full_cycles_before_bankrupcy * (long long)cycle_length + which_turn - 1) * n); // cerr << i << " " << solutions.back() << endl; } if (solutions.empty()) cout << -1 << endl; else cout << *min_element(solutions.begin(), solutions.end()) << endl; } |