#include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <algorithm> #include <set> #include <time.h> #include <queue> using namespace std; typedef long long int int64; typedef struct { vector<int64> indices; vector<int64> values; vector<int64> pref_min, suf_min; map<int64, vector<int64> > values_map; int64 min_value; } Cycle; int main () { int64 n, m, a; scanf("%lld", &n); vector<int64> start; start.reserve(n + 4); for (int64 i = 0; i < n; ++i) { scanf("%lld", &a); start.push_back(a); } scanf("%lld", &m); char c; vector<int64> machine_cycle; machine_cycle.reserve(m + 4); scanf("%c", &c); for (int64 i = 0; i < m; ++i) { scanf("%c", &c); machine_cycle.push_back(c == 'W' ? 1 : -1); } vector<int64> cycle_number(m, -1); vector<int64> order_in_cycle(m, -1); Cycle empty; empty.min_value = 1; vector<Cycle> cycles; for (int64 i = 0; i < m; ++i) { if (cycle_number[i] != -1) { continue; } int64 k = 0; int64 value = 0; int64 cnum = cycles.size(); cycle_number[i] = cnum; order_in_cycle[i] = 0; cycles.push_back(empty); cycles[cnum].indices.push_back(i); value += machine_cycle[i]; cycles[cnum].values.push_back(value); cycles[cnum].values_map[value].push_back(k); cycles[cnum].min_value = min(cycles[cnum].min_value, value); int64 j = (i + n) % m; while (j != i) { ++k; order_in_cycle[j] = k; cycle_number[j] = i; cycles[cnum].indices.push_back(j); value += machine_cycle[j]; cycles[cnum].values.push_back(value); cycles[cnum].values_map[value].push_back(k); cycles[cnum].min_value = min(cycles[cnum].min_value, value); j = (j + n) % m; } } for (int64 i = 0; i < cycles.size(); ++i) { int64 pref_min = cycles[i].values[0]; for (int64 j = 0; j < cycles[i].values.size(); ++j) { pref_min = min(pref_min, cycles[i].values[j]); cycles[i].pref_min.push_back(pref_min); } int64 suf_min = cycles[i].values[cycles[i].values.size() - 1]; for (int64 j = 0; j < cycles[i].values.size(); ++j) { suf_min = min(suf_min, cycles[i].values[cycles[i].values.size() - 1 - j]); cycles[i].suf_min.push_back(suf_min); } } int64 min_bank = -1LL; for (int64 i = 0; i < n; ++i) { int64 cycle = cycle_number[i % m]; int64 offset = order_in_cycle[i % m]; int64 s = start[i]; int64 suf_min = cycles[cycle].suf_min[cycles[cycle].values.size() - offset - 1]; int64 value = (offset ? cycles[cycle].values[offset - 1] : 0); int64 pref_min = cycles[cycle].pref_min[offset - 1]; int64 last = cycles[cycle].values[cycles[cycle].values.size() - 1]; int64 min_drop = min(suf_min - value, pref_min - value + last); int64 extra_cycles = 0LL; if ((last >= 0) && (-min_drop < s)) { continue; } else if (last < 0) { int64 num = s + min_drop; int64 den = -last; if (num > 0) { int64 q = num % den; int64 val = q ? num / den + 1 : num / den; extra_cycles = max(0LL, val); } } int64 rounds = extra_cycles * cycles[cycle].values.size(); s += last * extra_cycles; int64 extra_rounds = 0; vector<int64>::iterator it = lower_bound(cycles[cycle].values_map[value - s].begin(), cycles[cycle].values_map[value - s].end(), offset); if (it == cycles[cycle].values_map[value - s].end()) { int64 bound = cycles[cycle].values_map[value - s - last][0]; extra_rounds = cycles[cycle].values.size() - offset + bound + 1; } else { extra_rounds = *it - offset + 1; } int64 plays = (rounds + extra_rounds - 1) * n + i + 1; if (min_bank == -1LL) { min_bank = plays; } min_bank = min(min_bank, plays); } printf("%lld\n", min_bank); 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 | #include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <algorithm> #include <set> #include <time.h> #include <queue> using namespace std; typedef long long int int64; typedef struct { vector<int64> indices; vector<int64> values; vector<int64> pref_min, suf_min; map<int64, vector<int64> > values_map; int64 min_value; } Cycle; int main () { int64 n, m, a; scanf("%lld", &n); vector<int64> start; start.reserve(n + 4); for (int64 i = 0; i < n; ++i) { scanf("%lld", &a); start.push_back(a); } scanf("%lld", &m); char c; vector<int64> machine_cycle; machine_cycle.reserve(m + 4); scanf("%c", &c); for (int64 i = 0; i < m; ++i) { scanf("%c", &c); machine_cycle.push_back(c == 'W' ? 1 : -1); } vector<int64> cycle_number(m, -1); vector<int64> order_in_cycle(m, -1); Cycle empty; empty.min_value = 1; vector<Cycle> cycles; for (int64 i = 0; i < m; ++i) { if (cycle_number[i] != -1) { continue; } int64 k = 0; int64 value = 0; int64 cnum = cycles.size(); cycle_number[i] = cnum; order_in_cycle[i] = 0; cycles.push_back(empty); cycles[cnum].indices.push_back(i); value += machine_cycle[i]; cycles[cnum].values.push_back(value); cycles[cnum].values_map[value].push_back(k); cycles[cnum].min_value = min(cycles[cnum].min_value, value); int64 j = (i + n) % m; while (j != i) { ++k; order_in_cycle[j] = k; cycle_number[j] = i; cycles[cnum].indices.push_back(j); value += machine_cycle[j]; cycles[cnum].values.push_back(value); cycles[cnum].values_map[value].push_back(k); cycles[cnum].min_value = min(cycles[cnum].min_value, value); j = (j + n) % m; } } for (int64 i = 0; i < cycles.size(); ++i) { int64 pref_min = cycles[i].values[0]; for (int64 j = 0; j < cycles[i].values.size(); ++j) { pref_min = min(pref_min, cycles[i].values[j]); cycles[i].pref_min.push_back(pref_min); } int64 suf_min = cycles[i].values[cycles[i].values.size() - 1]; for (int64 j = 0; j < cycles[i].values.size(); ++j) { suf_min = min(suf_min, cycles[i].values[cycles[i].values.size() - 1 - j]); cycles[i].suf_min.push_back(suf_min); } } int64 min_bank = -1LL; for (int64 i = 0; i < n; ++i) { int64 cycle = cycle_number[i % m]; int64 offset = order_in_cycle[i % m]; int64 s = start[i]; int64 suf_min = cycles[cycle].suf_min[cycles[cycle].values.size() - offset - 1]; int64 value = (offset ? cycles[cycle].values[offset - 1] : 0); int64 pref_min = cycles[cycle].pref_min[offset - 1]; int64 last = cycles[cycle].values[cycles[cycle].values.size() - 1]; int64 min_drop = min(suf_min - value, pref_min - value + last); int64 extra_cycles = 0LL; if ((last >= 0) && (-min_drop < s)) { continue; } else if (last < 0) { int64 num = s + min_drop; int64 den = -last; if (num > 0) { int64 q = num % den; int64 val = q ? num / den + 1 : num / den; extra_cycles = max(0LL, val); } } int64 rounds = extra_cycles * cycles[cycle].values.size(); s += last * extra_cycles; int64 extra_rounds = 0; vector<int64>::iterator it = lower_bound(cycles[cycle].values_map[value - s].begin(), cycles[cycle].values_map[value - s].end(), offset); if (it == cycles[cycle].values_map[value - s].end()) { int64 bound = cycles[cycle].values_map[value - s - last][0]; extra_rounds = cycles[cycle].values.size() - offset + bound + 1; } else { extra_rounds = *it - offset + 1; } int64 plays = (rounds + extra_rounds - 1) * n + i + 1; if (min_bank == -1LL) { min_bank = plays; } min_bank = min(min_bank, plays); } printf("%lld\n", min_bank); return 0; } |