#include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) #define SIZE(s) ((int) (s).size()) #define SCAND(x) assert(scanf("%d", x) == 1) #define SCANS(x) assert(scanf("%s", x) == 1) #define ALL(s) s.begin(), s.end() #define MP make_pair #define ST first #define ND second #define VAR(x) if(0) cout << #x << " = " << x << endl using LL = long long; using PII = pair<int, int>; const int N = 1e6; const int M = 1e6; int n; int cash[N]; int m; char w[M+1]; int minint(int a, int b){return min(a, b);} struct event { int i; // where to put result int r; // value we look for event(int i, int r):i(i),r(r){} }; struct query { int i; // guy index (to access cash[i]) int x; // x of first occurrence in graph query(int i, int x):i(i),x(x){} }; struct cyclic { cyclic(vector<int> ds):k(ds.size()), fs(k + 1), pm(k), sm(k){ partial_sum(ALL(ds), fs.begin() + 1); partial_sum(fs.begin(), fs.end() - 1, pm.begin(), minint); partial_sum(fs.rbegin() + 1, fs.rend(), sm.rbegin(), minint); } vector<LL> solve(vector<query> qs){ vector<vector<event>> events(k); vector<LL> result(qs.size()); int d = fs[0] - fs.back(); int minval = min(sm[0] - d, sm[0]); REP(i, SIZE(qs)){ int x = qs[i].x; int s = cash[qs[i].i]; int l = max(fs[x] - sm[x], fs[x] - fs.back() + fs[0] - pm[x]); int t; if(l > s) t = 0; else if(d <= 0) t = -1; else t = (s-l+d-1)/d; if(t != -1){ result[i] = qs[i].i + ((LL) t * k - 1) * n; events[x].emplace_back(i, fs[x] - s + d * t); } else { result[i] = -1; } } vector<vector<int>> listeners(2*k); REP(i, k){ for(event e : events[i]) listeners[e.r - minval].push_back(e.i); for(int li : listeners[fs[i] - minval]) result[li] += (LL) n * (i - qs[li].x); listeners[fs[i] - minval].clear(); } REP(i, k){ for(int li : listeners[fs[i] - d - minval]) result[li] += (LL) n * (i + k - qs[li].x); listeners[fs[i] - d - minval].clear(); } return result; } int k; vector<int> fs; vector<int> pm; vector<int> sm; }; vector<cyclic> cyclics; vector<vector<query>> qss; int cidx[M]; void makecyclic(int begin){ vector<int> ds; for(int i = begin; ds.empty() || i != begin; i = (i + n) % m){ cidx[i] = ds.size(); if(w[i] == 'P') ds.push_back(-1); else if(w[i] == 'W') ds.push_back(+1); else assert(0); } cyclics.emplace_back(ds); } int main(){ SCAND(&n); REP(i, n) SCAND(&cash[i]); SCAND(&m); SCANS(w); assert((int) strlen(w) == m); int c = __gcd(n, m); REP(i, c) makecyclic(i); qss.resize(c); REP(i, n){ qss[i%cyclics.size()].emplace_back(i, cidx[i%m]); } LL result = 0; REP(i, c){ vector<LL> v = cyclics[i].solve(qss[i]); for(LL ll : v) if(ll != -1){ if(result == 0) result = ll; else result = min(result, ll); } } printf("%lld\n", (result == 0) ? -1 : result+1); }
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 | #include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (n); i++) #define SIZE(s) ((int) (s).size()) #define SCAND(x) assert(scanf("%d", x) == 1) #define SCANS(x) assert(scanf("%s", x) == 1) #define ALL(s) s.begin(), s.end() #define MP make_pair #define ST first #define ND second #define VAR(x) if(0) cout << #x << " = " << x << endl using LL = long long; using PII = pair<int, int>; const int N = 1e6; const int M = 1e6; int n; int cash[N]; int m; char w[M+1]; int minint(int a, int b){return min(a, b);} struct event { int i; // where to put result int r; // value we look for event(int i, int r):i(i),r(r){} }; struct query { int i; // guy index (to access cash[i]) int x; // x of first occurrence in graph query(int i, int x):i(i),x(x){} }; struct cyclic { cyclic(vector<int> ds):k(ds.size()), fs(k + 1), pm(k), sm(k){ partial_sum(ALL(ds), fs.begin() + 1); partial_sum(fs.begin(), fs.end() - 1, pm.begin(), minint); partial_sum(fs.rbegin() + 1, fs.rend(), sm.rbegin(), minint); } vector<LL> solve(vector<query> qs){ vector<vector<event>> events(k); vector<LL> result(qs.size()); int d = fs[0] - fs.back(); int minval = min(sm[0] - d, sm[0]); REP(i, SIZE(qs)){ int x = qs[i].x; int s = cash[qs[i].i]; int l = max(fs[x] - sm[x], fs[x] - fs.back() + fs[0] - pm[x]); int t; if(l > s) t = 0; else if(d <= 0) t = -1; else t = (s-l+d-1)/d; if(t != -1){ result[i] = qs[i].i + ((LL) t * k - 1) * n; events[x].emplace_back(i, fs[x] - s + d * t); } else { result[i] = -1; } } vector<vector<int>> listeners(2*k); REP(i, k){ for(event e : events[i]) listeners[e.r - minval].push_back(e.i); for(int li : listeners[fs[i] - minval]) result[li] += (LL) n * (i - qs[li].x); listeners[fs[i] - minval].clear(); } REP(i, k){ for(int li : listeners[fs[i] - d - minval]) result[li] += (LL) n * (i + k - qs[li].x); listeners[fs[i] - d - minval].clear(); } return result; } int k; vector<int> fs; vector<int> pm; vector<int> sm; }; vector<cyclic> cyclics; vector<vector<query>> qss; int cidx[M]; void makecyclic(int begin){ vector<int> ds; for(int i = begin; ds.empty() || i != begin; i = (i + n) % m){ cidx[i] = ds.size(); if(w[i] == 'P') ds.push_back(-1); else if(w[i] == 'W') ds.push_back(+1); else assert(0); } cyclics.emplace_back(ds); } int main(){ SCAND(&n); REP(i, n) SCAND(&cash[i]); SCAND(&m); SCANS(w); assert((int) strlen(w) == m); int c = __gcd(n, m); REP(i, c) makecyclic(i); qss.resize(c); REP(i, n){ qss[i%cyclics.size()].emplace_back(i, cidx[i%m]); } LL result = 0; REP(i, c){ vector<LL> v = cyclics[i].solve(qss[i]); for(LL ll : v) if(ll != -1){ if(result == 0) result = ll; else result = min(result, ll); } } printf("%lld\n", (result == 0) ? -1 : result+1); } |