#ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include <cstdio> #include <set> #include <vector> #define MAX 1000001 using namespace std; int friends[MAX]; long long friendRounds[MAX]; char slots[MAX]; int cycleId[MAX]; int cycleDelta[MAX]; int cycleSize[MAX]; int order[MAX]; int values[MAX]; int dips[MAX]; int main() { int n, m; scanf("%d\n", &n); for (int i = 0; i < n; i++) { scanf("%d", friends + i); } scanf("%d\n", &m); for (int i = 0; i < m; i++) { scanf("%c", slots + i); cycleId[i] = -1; cycleDelta[i] = MAX; dips[i] = MAX; } for (int i = 0; i < m; i++) { int pos = i; int size = 0; int delta = 0; set<pair<int, int>> valueSet; while (cycleId[pos] == -1) { values[pos] = delta; valueSet.insert(make_pair(delta, pos)); delta += (slots[pos] == 'W') ? 1 : -1; cycleId[pos] = i; size++; pos = (pos + n) % m; } pos = i; while (dips[pos] == MAX) { int lowest = valueSet.begin()->first; dips[pos] = lowest - values[pos]; if (dips[pos] > 0) { dips[pos] = 0; } valueSet.erase(make_pair(values[pos], pos)); valueSet.insert(make_pair(values[pos] + delta, pos)); pos = (pos + n) % m; } cycleDelta[i] = delta != 0 ? delta : cycleDelta[cycleId[i]]; cycleSize[i] = size != 0 ? size : cycleSize[cycleId[i]]; } int cycle = 0; vector<set<pair<int, int>>> cycleGraphs; while (cycleId[cycle] == cycle) { set<pair<int, int>> newSet; cycleGraphs.push_back(newSet); int pos = cycle; int delta = 0; for (int i = 0; i < cycleSize[cycle] * 2; i++) { if (i < cycleSize[cycle]) { order[pos] = i; } cycleGraphs[cycle].insert(make_pair(delta, i)); delta += slots[pos] == 'W' ? 1 : -1; pos = (pos + n) % m; } cycle++; } long long lowest = 2000000000000000000; for (int i = 0; i < n; i++) { friendRounds[i] = 0; int savings = friends[i]; int start = i % m; int delta = cycleDelta[start]; int dip = dips[start]; if (savings > -dip) { if (delta < 0) { friendRounds[i] = (savings + dip - 1) / -delta + 1; } else { friendRounds[i] = -1; } } if (friendRounds[i] != -1) { int id = cycleId[start]; long long rounds = (long long)friendRounds[i] * cycleSize[start]; int pos = order[start]; int startingValue = values[start]; int targetValue = startingValue - savings - delta * friendRounds[i]; auto lowerBound = cycleGraphs[id].lower_bound(make_pair(targetValue, pos)); friendRounds[i] = ((long long)(rounds + lowerBound->second - pos - 1)) * ((long long)n) + i + 1; if (friendRounds[i] < lowest) lowest = friendRounds[i]; } } printf("%lld\n", lowest != 2000000000000000000 ? lowest : -1); 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 | #ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include <cstdio> #include <set> #include <vector> #define MAX 1000001 using namespace std; int friends[MAX]; long long friendRounds[MAX]; char slots[MAX]; int cycleId[MAX]; int cycleDelta[MAX]; int cycleSize[MAX]; int order[MAX]; int values[MAX]; int dips[MAX]; int main() { int n, m; scanf("%d\n", &n); for (int i = 0; i < n; i++) { scanf("%d", friends + i); } scanf("%d\n", &m); for (int i = 0; i < m; i++) { scanf("%c", slots + i); cycleId[i] = -1; cycleDelta[i] = MAX; dips[i] = MAX; } for (int i = 0; i < m; i++) { int pos = i; int size = 0; int delta = 0; set<pair<int, int>> valueSet; while (cycleId[pos] == -1) { values[pos] = delta; valueSet.insert(make_pair(delta, pos)); delta += (slots[pos] == 'W') ? 1 : -1; cycleId[pos] = i; size++; pos = (pos + n) % m; } pos = i; while (dips[pos] == MAX) { int lowest = valueSet.begin()->first; dips[pos] = lowest - values[pos]; if (dips[pos] > 0) { dips[pos] = 0; } valueSet.erase(make_pair(values[pos], pos)); valueSet.insert(make_pair(values[pos] + delta, pos)); pos = (pos + n) % m; } cycleDelta[i] = delta != 0 ? delta : cycleDelta[cycleId[i]]; cycleSize[i] = size != 0 ? size : cycleSize[cycleId[i]]; } int cycle = 0; vector<set<pair<int, int>>> cycleGraphs; while (cycleId[cycle] == cycle) { set<pair<int, int>> newSet; cycleGraphs.push_back(newSet); int pos = cycle; int delta = 0; for (int i = 0; i < cycleSize[cycle] * 2; i++) { if (i < cycleSize[cycle]) { order[pos] = i; } cycleGraphs[cycle].insert(make_pair(delta, i)); delta += slots[pos] == 'W' ? 1 : -1; pos = (pos + n) % m; } cycle++; } long long lowest = 2000000000000000000; for (int i = 0; i < n; i++) { friendRounds[i] = 0; int savings = friends[i]; int start = i % m; int delta = cycleDelta[start]; int dip = dips[start]; if (savings > -dip) { if (delta < 0) { friendRounds[i] = (savings + dip - 1) / -delta + 1; } else { friendRounds[i] = -1; } } if (friendRounds[i] != -1) { int id = cycleId[start]; long long rounds = (long long)friendRounds[i] * cycleSize[start]; int pos = order[start]; int startingValue = values[start]; int targetValue = startingValue - savings - delta * friendRounds[i]; auto lowerBound = cycleGraphs[id].lower_bound(make_pair(targetValue, pos)); friendRounds[i] = ((long long)(rounds + lowerBound->second - pos - 1)) * ((long long)n) + i + 1; if (friendRounds[i] < lowest) lowest = friendRounds[i]; } } printf("%lld\n", lowest != 2000000000000000000 ? lowest : -1); return 0; } |