#include <bits/stdc++.h> using namespace std; long long k[1000007]; char cykl[1000007]; bool odw[2000007]; long long a[2000007]; long long b[2000007]; long long n[2000007]; pair<int,int> do_ktorego[2000007]; long long cykle[20000007]; long long od_ktorego[2000007]; long long minimum_na_cyklu[2000007]; int main() { long long N,M; scanf("%lld",&N); for (long long i = 0;i < N;i++) { scanf("%lld",&k[i]); } scanf("%lld",&M); scanf("%s",cykl); long long liczba_cykli = __gcd(N,M); long long dlugosc_cykli = M/__gcd(N,M); long long il; int cmmm = 0; for (int i = 0;i < M;i++) { if (!odw[i]) { il = 0; for (int s = 0,w = i;s < dlugosc_cykli*2;s++,w=(w+N)%M) { odw[w] = true; od_ktorego[cmmm*dlugosc_cykli+s] = w; do_ktorego[w] = make_pair(cmmm,s%M); if (cykl[w] == 'W') il++; else il--; cykle[cmmm*dlugosc_cykli+s] = il; } cmmm++; } } for (long long i = 0;i < liczba_cykli;i++) { minimum_na_cyklu[i*dlugosc_cykli+dlugosc_cykli] = cykle[i*dlugosc_cykli+dlugosc_cykli]; minimum_na_cyklu[i*dlugosc_cykli+dlugosc_cykli-1] = cykle[i*dlugosc_cykli+dlugosc_cykli-1]; for (long long w = dlugosc_cykli-2;w >= 0;w--) { minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w+1],cykle[i*dlugosc_cykli+w]); } for (long long w = dlugosc_cykli+1;w < dlugosc_cykli*2;w++) { minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w-1],cykle[i*dlugosc_cykli+w]); } } for (long long i = 0;i < liczba_cykli;i++) { for (long long w = 0;w < dlugosc_cykli;w++) { a[od_ktorego[i*dlugosc_cykli+w]] = cykle[i*dlugosc_cykli+dlugosc_cykli-1]; b[od_ktorego[i*dlugosc_cykli+w]] = min(minimum_na_cyklu[i*dlugosc_cykli+w],minimum_na_cyklu[i*dlugosc_cykli+w+dlugosc_cykli-1])-cykle[i*dlugosc_cykli+w-1]; } b[od_ktorego[i*dlugosc_cykli+0]] = minimum_na_cyklu[i*dlugosc_cykli+0]; } long long minimum = 100000000007; for (long long i = 0;i < N;i++) { if (k[i] <= -b[i%M]) n[i] = 0; else if (a[i%M] < 0) n[i] = (k[i]+b[i%M]-a[i%M]-1)/(-a[i%M]); else n[i] = -1; if (n[i] != -1) minimum = min(minimum,n[i]); } for (long long i = 0;i < liczba_cykli;i++) { minimum_na_cyklu[i*dlugosc_cykli+0] = cykle[i*dlugosc_cykli+0]; for (long long w = 1;w < dlugosc_cykli*2;w++) minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w-1],cykle[i*dlugosc_cykli+w]); } if (minimum == 100000000007) { printf("-1"); return 0; } long long pocz,sr,kon; long long kt; long long f; long long megamini = 1000000000007; long long odjo; long long pp; for (int i = 0;i < N;i++) { if (n[i] == minimum) { kt = do_ktorego[i].first; pocz = do_ktorego[i].second-1; kon = pocz+dlugosc_cykli+1; odjo = a[i]*n[i]; pp = pocz; if (pocz != -1) f = cykle[kt*dlugosc_cykli+pocz]; else f = 0; while (pocz+1 != kon) { sr = (pocz+kon)/2; if (-(minimum_na_cyklu[kt*dlugosc_cykli+sr]-f) >= k[i]+odjo) kon = sr; else pocz = sr; } megamini = min(megamini,((kon-pp-1)*N)+i+1); } } printf("%lld",(minimum*N*dlugosc_cykli)+megamini); 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 | #include <bits/stdc++.h> using namespace std; long long k[1000007]; char cykl[1000007]; bool odw[2000007]; long long a[2000007]; long long b[2000007]; long long n[2000007]; pair<int,int> do_ktorego[2000007]; long long cykle[20000007]; long long od_ktorego[2000007]; long long minimum_na_cyklu[2000007]; int main() { long long N,M; scanf("%lld",&N); for (long long i = 0;i < N;i++) { scanf("%lld",&k[i]); } scanf("%lld",&M); scanf("%s",cykl); long long liczba_cykli = __gcd(N,M); long long dlugosc_cykli = M/__gcd(N,M); long long il; int cmmm = 0; for (int i = 0;i < M;i++) { if (!odw[i]) { il = 0; for (int s = 0,w = i;s < dlugosc_cykli*2;s++,w=(w+N)%M) { odw[w] = true; od_ktorego[cmmm*dlugosc_cykli+s] = w; do_ktorego[w] = make_pair(cmmm,s%M); if (cykl[w] == 'W') il++; else il--; cykle[cmmm*dlugosc_cykli+s] = il; } cmmm++; } } for (long long i = 0;i < liczba_cykli;i++) { minimum_na_cyklu[i*dlugosc_cykli+dlugosc_cykli] = cykle[i*dlugosc_cykli+dlugosc_cykli]; minimum_na_cyklu[i*dlugosc_cykli+dlugosc_cykli-1] = cykle[i*dlugosc_cykli+dlugosc_cykli-1]; for (long long w = dlugosc_cykli-2;w >= 0;w--) { minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w+1],cykle[i*dlugosc_cykli+w]); } for (long long w = dlugosc_cykli+1;w < dlugosc_cykli*2;w++) { minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w-1],cykle[i*dlugosc_cykli+w]); } } for (long long i = 0;i < liczba_cykli;i++) { for (long long w = 0;w < dlugosc_cykli;w++) { a[od_ktorego[i*dlugosc_cykli+w]] = cykle[i*dlugosc_cykli+dlugosc_cykli-1]; b[od_ktorego[i*dlugosc_cykli+w]] = min(minimum_na_cyklu[i*dlugosc_cykli+w],minimum_na_cyklu[i*dlugosc_cykli+w+dlugosc_cykli-1])-cykle[i*dlugosc_cykli+w-1]; } b[od_ktorego[i*dlugosc_cykli+0]] = minimum_na_cyklu[i*dlugosc_cykli+0]; } long long minimum = 100000000007; for (long long i = 0;i < N;i++) { if (k[i] <= -b[i%M]) n[i] = 0; else if (a[i%M] < 0) n[i] = (k[i]+b[i%M]-a[i%M]-1)/(-a[i%M]); else n[i] = -1; if (n[i] != -1) minimum = min(minimum,n[i]); } for (long long i = 0;i < liczba_cykli;i++) { minimum_na_cyklu[i*dlugosc_cykli+0] = cykle[i*dlugosc_cykli+0]; for (long long w = 1;w < dlugosc_cykli*2;w++) minimum_na_cyklu[i*dlugosc_cykli+w] = min(minimum_na_cyklu[i*dlugosc_cykli+w-1],cykle[i*dlugosc_cykli+w]); } if (minimum == 100000000007) { printf("-1"); return 0; } long long pocz,sr,kon; long long kt; long long f; long long megamini = 1000000000007; long long odjo; long long pp; for (int i = 0;i < N;i++) { if (n[i] == minimum) { kt = do_ktorego[i].first; pocz = do_ktorego[i].second-1; kon = pocz+dlugosc_cykli+1; odjo = a[i]*n[i]; pp = pocz; if (pocz != -1) f = cykle[kt*dlugosc_cykli+pocz]; else f = 0; while (pocz+1 != kon) { sr = (pocz+kon)/2; if (-(minimum_na_cyklu[kt*dlugosc_cykli+sr]-f) >= k[i]+odjo) kon = sr; else pocz = sr; } megamini = min(megamini,((kon-pp-1)*N)+i+1); } } printf("%lld",(minimum*N*dlugosc_cykli)+megamini); return 0; } |