#include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long ULL; const int N=1000*1000+7; const int OFFSET = 2*N; int M=1; const ULL MAX = ULL(1000*1000*1000)*ULL(1000*1000*1000); char buf[N]; int money[N]; int wins[N]; int prizes[2*N]; int tree[1024*1024*4+7]; vector<int>place_with_value[4*N]; ULL wyn = MAX; int gcd (int a, int b) { while (b!=0) { int tmp = a%b; a = b; b = tmp; } return a; if (b==0) return a; } int get_min (int p, int k) { int w; p+=M; k+=M; w = min (tree[p], tree[k]); while (p/2!=k/2) { if (!(p&1)) w = min (w, tree[p+1]); if (k&1) w = min (w, tree[k-1]); p/=2; k/=2; } return w; } int main () { ULL n, m; scanf("%lld", &n); for (int i=0; i<n; i++) scanf("%d", &money[i]); scanf("%lld", &m); scanf("%s", buf); for (int i=0; i<m; i++) wins[i] = (buf[i] == 'W' ? 1 : -1); ULL group_size = gcd(n, m); ULL small_n = n/group_size; ULL small_m = m/group_size; while (M <= small_n+small_m) M<<=1; for (int g=0; g<group_size; g++) { //rozwinięte ceny prizes[0] = 0; for (int i=0; i<2*M; i++) tree[i] = 1000*1000*1000; for (int i=1; i<=small_n+small_m; i++) tree[i+M] = prizes[i] = prizes[i-1] + wins[(((i-1)*small_n)%small_m) * group_size + g]; for (int i=M-1; i>0; i--) tree[i] = min (tree[i*2], tree[i*2+1]); int sum = prizes[small_m]; for (int j=-small_m-small_n; j<=small_m+small_n; j++) place_with_value[j+OFFSET].clear(); for (int i=1; i<=small_n+small_m; i++) place_with_value[prizes[i]+OFFSET].push_back(i); for (int i=0; i<small_n; i++) //normalnej kolejności, chcemy znać indeks rozwinięcia { int w = i * group_size + g; int k = (i*small_n)%small_m; int value = money[w]; int min_value = get_min(k+1, k+small_m)-prizes[k]; if (min_value+value > 0 && sum>=0) continue; ULL wyn_t = 0; if (min_value + value > 0) { wyn_t = (value+min_value-1-sum)/(-sum); value += wyn_t*sum; wyn_t *= small_m; } wyn_t += *upper_bound(place_with_value[OFFSET + prizes[k]-value].begin(), place_with_value[OFFSET + prizes[k]-value].end(), k) - k; /* for (auto e : place_with_value[OFFSET + prizes[k]-value]) if (e > k) { wyn_t += e-k; break; }*/ wyn = min (wyn, (wyn_t-1) * n + w + 1); } } printf("%lld\n", wyn == MAX ? -1 : wyn); 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 | #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long ULL; const int N=1000*1000+7; const int OFFSET = 2*N; int M=1; const ULL MAX = ULL(1000*1000*1000)*ULL(1000*1000*1000); char buf[N]; int money[N]; int wins[N]; int prizes[2*N]; int tree[1024*1024*4+7]; vector<int>place_with_value[4*N]; ULL wyn = MAX; int gcd (int a, int b) { while (b!=0) { int tmp = a%b; a = b; b = tmp; } return a; if (b==0) return a; } int get_min (int p, int k) { int w; p+=M; k+=M; w = min (tree[p], tree[k]); while (p/2!=k/2) { if (!(p&1)) w = min (w, tree[p+1]); if (k&1) w = min (w, tree[k-1]); p/=2; k/=2; } return w; } int main () { ULL n, m; scanf("%lld", &n); for (int i=0; i<n; i++) scanf("%d", &money[i]); scanf("%lld", &m); scanf("%s", buf); for (int i=0; i<m; i++) wins[i] = (buf[i] == 'W' ? 1 : -1); ULL group_size = gcd(n, m); ULL small_n = n/group_size; ULL small_m = m/group_size; while (M <= small_n+small_m) M<<=1; for (int g=0; g<group_size; g++) { //rozwinięte ceny prizes[0] = 0; for (int i=0; i<2*M; i++) tree[i] = 1000*1000*1000; for (int i=1; i<=small_n+small_m; i++) tree[i+M] = prizes[i] = prizes[i-1] + wins[(((i-1)*small_n)%small_m) * group_size + g]; for (int i=M-1; i>0; i--) tree[i] = min (tree[i*2], tree[i*2+1]); int sum = prizes[small_m]; for (int j=-small_m-small_n; j<=small_m+small_n; j++) place_with_value[j+OFFSET].clear(); for (int i=1; i<=small_n+small_m; i++) place_with_value[prizes[i]+OFFSET].push_back(i); for (int i=0; i<small_n; i++) //normalnej kolejności, chcemy znać indeks rozwinięcia { int w = i * group_size + g; int k = (i*small_n)%small_m; int value = money[w]; int min_value = get_min(k+1, k+small_m)-prizes[k]; if (min_value+value > 0 && sum>=0) continue; ULL wyn_t = 0; if (min_value + value > 0) { wyn_t = (value+min_value-1-sum)/(-sum); value += wyn_t*sum; wyn_t *= small_m; } wyn_t += *upper_bound(place_with_value[OFFSET + prizes[k]-value].begin(), place_with_value[OFFSET + prizes[k]-value].end(), k) - k; /* for (auto e : place_with_value[OFFSET + prizes[k]-value]) if (e > k) { wyn_t += e-k; break; }*/ wyn = min (wyn, (wyn_t-1) * n + w + 1); } } printf("%lld\n", wyn == MAX ? -1 : wyn); return 0; } |