#include <algorithm> #include <cstdio> #include <vector> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N_MAX = 1e6+10; const int M_MAX = 1e6+10; int n, c[N_MAX], m; char a[M_MAX]; vector<vector<int>> cycles; int cycle[N_MAX]; bool cycle_used[M_MAX]; int cycle_pos[M_MAX]; void build_cycle() { for (int i = 0; i < n; i++) { int p = i % m; if (cycle_used[p]) { cycle[i] = cycle[p]; } else { cycle[i] = cycles.size(); vector<int> new_cycle; int pos = 0; do { new_cycle.push_back(p); cycle[p % n] = cycle[i]; cycle_pos[p] = pos; cycle_used[p] = true; p = (p + n) % m; pos++; } while (p != (i % m)); cycles.push_back(new_cycle); } } // for (int i = 0; i < n; i++) { // printf("%c [cycle=%d, start=%d]\n", 'A'+i, cycle[i], cycle_pos[i % m]); // } // for (auto c : cycles) { // printf("cycle="); // for (auto x : c) printf("%d ", x); // printf("\n"); // } } void double_cycle() { for (auto& cc : cycles) { int k = cc.size(); for (int i = 0; i < k; i++) cc.push_back(cc[i]); } } ll lost_slow(int p) { } ll lost(int p) { vector<int>& cc = cycles[cycle[p]]; int h = c[p]; ll t; int i; for (t = (p+1), i = cycle_pos[p % m]; t < 1000000; t += n, i = (i+1) % cc.size()) { h += (a[cc[i]] == 'W' ? 1 : -1); if (h == 0) { return t; } } return -1; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", c+i); scanf("%d", &m); scanf("%s", a); build_cycle(); ll ans = -1; for (int i = 0; i < n; i++) { ll res = lost(i); // printf("lost(%d) %lld\n", i, res); // res = lost_slow(i); // printf("lost(%d) %lld\n", i, res); if (res != -1) { ans = (ans == -1) ? res : min(ans, res); } } printf("%lld\n", ans); 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 | #include <algorithm> #include <cstdio> #include <vector> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N_MAX = 1e6+10; const int M_MAX = 1e6+10; int n, c[N_MAX], m; char a[M_MAX]; vector<vector<int>> cycles; int cycle[N_MAX]; bool cycle_used[M_MAX]; int cycle_pos[M_MAX]; void build_cycle() { for (int i = 0; i < n; i++) { int p = i % m; if (cycle_used[p]) { cycle[i] = cycle[p]; } else { cycle[i] = cycles.size(); vector<int> new_cycle; int pos = 0; do { new_cycle.push_back(p); cycle[p % n] = cycle[i]; cycle_pos[p] = pos; cycle_used[p] = true; p = (p + n) % m; pos++; } while (p != (i % m)); cycles.push_back(new_cycle); } } // for (int i = 0; i < n; i++) { // printf("%c [cycle=%d, start=%d]\n", 'A'+i, cycle[i], cycle_pos[i % m]); // } // for (auto c : cycles) { // printf("cycle="); // for (auto x : c) printf("%d ", x); // printf("\n"); // } } void double_cycle() { for (auto& cc : cycles) { int k = cc.size(); for (int i = 0; i < k; i++) cc.push_back(cc[i]); } } ll lost_slow(int p) { } ll lost(int p) { vector<int>& cc = cycles[cycle[p]]; int h = c[p]; ll t; int i; for (t = (p+1), i = cycle_pos[p % m]; t < 1000000; t += n, i = (i+1) % cc.size()) { h += (a[cc[i]] == 'W' ? 1 : -1); if (h == 0) { return t; } } return -1; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", c+i); scanf("%d", &m); scanf("%s", a); build_cycle(); ll ans = -1; for (int i = 0; i < n; i++) { ll res = lost(i); // printf("lost(%d) %lld\n", i, res); // res = lost_slow(i); // printf("lost(%d) %lld\n", i, res); if (res != -1) { ans = (ans == -1) ? res : min(ans, res); } } printf("%lld\n", ans); return 0; } |