#include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef unsigned long long ull; #define INF ((ull)-1) const int MX = 1000006; int n, m; int P[MX]; char s[2*MX]; int wyn(int i) { return s[i] == 'W' ? 1 : -1; } bool b[MX]; struct Cykl { vector<int> sum, gi; struct Gracz { int i, p, x, min, t, r; Gracz() : x(0), min(0), t(0), r(0) {} Gracz(int _i, int _x) : i(_i), p(P[_i]), x(_x), min(0), t(0), r(0) {} }; vector< Gracz > g; Cykl() : sum(1,0) {} void add(int i) { if (i < n) { b[i] = true; gi.push_back(g.size()); g.push_back(Gracz(i, ((int)sum.size())-1)); } else gi.push_back(-1); sum.push_back(sum.back() + wyn(i)); } ull calc() { vector<int> lmin(sum.size()), rmin(sum.size()); lmin[0] = 0; for (int i=1; i<sum.size(); i++) lmin[i] = min(lmin[i-1], sum[i]); rmin[sum.size()-1] = 0; for (int i=sum.size()-2; i>=0; i--) rmin[i] = min(rmin[i+1], sum[i]); const int d = sum.back(); ull w = INF; int mint = MX; for (int i=0; i<g.size(); i++) { int x = g[i].x; g[i].min = min(rmin[x], d + lmin[x]) - sum[x]; if (d >= 0) g[i].t = 0; else g[i].t = max(0, g[i].p - (d - g[i].min) - 1) / -d; if (g[i].t < mint) mint = g[i].t; g[i].r = g[i].p + g[i].t * d; } gi.push_back(-1); gi.resize(gi.size()*2, -1); int ss = sum.size(); sum.resize(sum.size()*2 - 1); for (int i=0; i<ss-1; i++) sum[ss+i] = sum[i+1] + d; priority_queue< pair<int, int> > q; for (int i=0; i<sum.size(); i++) { if (gi[i] >= 0) { int j = gi[i]; if (g[j].t == mint) q.push(make_pair(sum[i] - g[j].r, j)); } while (!q.empty() && q.top().first == sum[i]) { int j = q.top().second; q.pop(); ull gw = (ull)g[j].i + ( (ull)g[j].t * (ull)(ss-1) + (ull)(i - g[j].x - 1) ) * (ull)n + (ull)1; w = min(w, gw); } } return w; } }; int main() { scanf("%d", &n); for (int i=0; i<n; i++) scanf("%d", P+i); scanf("%d", &m); scanf("%s", s); ull w = INF; int mm = m; while (n > m) { for (int i=m; i<m+mm; i++) s[i] = s[i-mm]; m += mm; } for (int i=0; i<min(n,m); i++) { if (b[i]) continue; int j=i; Cykl c; do { c.add(j); } while (i != (j=(j+n)%m)); ull cw = c.calc(); if (cw < w) w = cw; } if (w == INF) printf("-1\n"); else printf("%llu\n", w); 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 | #include<cstdio> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef unsigned long long ull; #define INF ((ull)-1) const int MX = 1000006; int n, m; int P[MX]; char s[2*MX]; int wyn(int i) { return s[i] == 'W' ? 1 : -1; } bool b[MX]; struct Cykl { vector<int> sum, gi; struct Gracz { int i, p, x, min, t, r; Gracz() : x(0), min(0), t(0), r(0) {} Gracz(int _i, int _x) : i(_i), p(P[_i]), x(_x), min(0), t(0), r(0) {} }; vector< Gracz > g; Cykl() : sum(1,0) {} void add(int i) { if (i < n) { b[i] = true; gi.push_back(g.size()); g.push_back(Gracz(i, ((int)sum.size())-1)); } else gi.push_back(-1); sum.push_back(sum.back() + wyn(i)); } ull calc() { vector<int> lmin(sum.size()), rmin(sum.size()); lmin[0] = 0; for (int i=1; i<sum.size(); i++) lmin[i] = min(lmin[i-1], sum[i]); rmin[sum.size()-1] = 0; for (int i=sum.size()-2; i>=0; i--) rmin[i] = min(rmin[i+1], sum[i]); const int d = sum.back(); ull w = INF; int mint = MX; for (int i=0; i<g.size(); i++) { int x = g[i].x; g[i].min = min(rmin[x], d + lmin[x]) - sum[x]; if (d >= 0) g[i].t = 0; else g[i].t = max(0, g[i].p - (d - g[i].min) - 1) / -d; if (g[i].t < mint) mint = g[i].t; g[i].r = g[i].p + g[i].t * d; } gi.push_back(-1); gi.resize(gi.size()*2, -1); int ss = sum.size(); sum.resize(sum.size()*2 - 1); for (int i=0; i<ss-1; i++) sum[ss+i] = sum[i+1] + d; priority_queue< pair<int, int> > q; for (int i=0; i<sum.size(); i++) { if (gi[i] >= 0) { int j = gi[i]; if (g[j].t == mint) q.push(make_pair(sum[i] - g[j].r, j)); } while (!q.empty() && q.top().first == sum[i]) { int j = q.top().second; q.pop(); ull gw = (ull)g[j].i + ( (ull)g[j].t * (ull)(ss-1) + (ull)(i - g[j].x - 1) ) * (ull)n + (ull)1; w = min(w, gw); } } return w; } }; int main() { scanf("%d", &n); for (int i=0; i<n; i++) scanf("%d", P+i); scanf("%d", &m); scanf("%s", s); ull w = INF; int mm = m; while (n > m) { for (int i=m; i<m+mm; i++) s[i] = s[i-mm]; m += mm; } for (int i=0; i<min(n,m); i++) { if (b[i]) continue; int j=i; Cykl c; do { c.add(j); } while (i != (j=(j+n)%m)); ull cw = c.calc(); if (cw < w) w = cw; } if (w == INF) printf("-1\n"); else printf("%llu\n", w); return 0; } |