#include <cstdio> #include <utility> #include <algorithm> const int MAX_N = 1000009; const int MAX_M = MAX_N; const int OFF = MAX_M-1; const long long INF = ((long long)MAX_M)*MAX_N*MAX_N; int a[MAX_N]; char wins[MAX_M]; struct list { int num; list* prev; list* next; }; list elem[MAX_N]; list* bl[MAX_M*2]; list* ab[MAX_M*2]; bool used[MAX_M]; bool checked[MAX_N]; void add(list*& head, list* elem) { if (!head) { head = elem; } else { elem->prev = head->prev; elem->next = head; head->prev->next = elem; head->prev = elem; } } void pop(list*& head) { if (!head) return; list* elem = head; if (elem->next == elem) { head = NULL; } else { head = elem->next; elem->next->prev = elem->prev; elem->prev->next = elem->next; } } int main() { int n, m; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); scanf("%d", &m); scanf("%s", wins); long long min = INF; for (int i = 0; i < n; ++i) { if (used[i%m]) continue; int rl = 0; int sum = 0; int max = 0; for (int cur = i%m; !used[cur]; cur = (cur+n)%m) { sum += (wins[cur] == 'P') ? 1 : -1; elem[rl] = {rl, &elem[rl], &elem[rl]}; add(bl[OFF+sum], &elem[rl]); used[cur] = true; if (sum > max) max = sum; ++rl; } int psum = 0; int cur = i%m; for (int j = 0; j < rl; ++j) { for (int id = cur; id < n && !checked[id]; id += m) { // przegrywa przed końcem cyklu int tl = a[id]; if (tl+psum < MAX_M && bl[OFF+tl+psum]) { min = std::min(min, ((long long)bl[OFF+tl+psum]->num-j)*n+id+1); } else { // dograj do końca cyklu tl -= sum-psum; // ile cykli musimy jeszcze rozegrać int cycles = 0; if (sum > 0 && tl > max) { cycles = (tl-max+sum-1)/sum; } tl -= cycles*sum; // gry = ile czekamy na kolejkę long long games = id+1; // + cykl dograny do końca games += ((long long)rl-j)*n; // + cykle które gramy całe games += ((long long)rl)*n*cycles; if (tl < MAX_M) { if (ab[OFF+tl]) { min = std::min(min, games+((long long)ab[OFF+tl]->num)*n); } else if (bl[OFF+tl]) { min = std::min(min, games+((long long)bl[OFF+tl]->num)*n); } } } checked[id] = true; } psum += (wins[cur] == 'P') ? 1 : -1; struct list* el = bl[OFF+psum]; pop(bl[OFF+psum]); add(ab[OFF+psum], el); cur = (cur+n)%m; } for (int j = max-rl; j <= max; ++j) { bl[OFF+j] = ab[OFF+j] = NULL; } } if (min == INF) { printf("-1\n"); } else { printf("%lld\n", min); } }
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 | #include <cstdio> #include <utility> #include <algorithm> const int MAX_N = 1000009; const int MAX_M = MAX_N; const int OFF = MAX_M-1; const long long INF = ((long long)MAX_M)*MAX_N*MAX_N; int a[MAX_N]; char wins[MAX_M]; struct list { int num; list* prev; list* next; }; list elem[MAX_N]; list* bl[MAX_M*2]; list* ab[MAX_M*2]; bool used[MAX_M]; bool checked[MAX_N]; void add(list*& head, list* elem) { if (!head) { head = elem; } else { elem->prev = head->prev; elem->next = head; head->prev->next = elem; head->prev = elem; } } void pop(list*& head) { if (!head) return; list* elem = head; if (elem->next == elem) { head = NULL; } else { head = elem->next; elem->next->prev = elem->prev; elem->prev->next = elem->next; } } int main() { int n, m; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); scanf("%d", &m); scanf("%s", wins); long long min = INF; for (int i = 0; i < n; ++i) { if (used[i%m]) continue; int rl = 0; int sum = 0; int max = 0; for (int cur = i%m; !used[cur]; cur = (cur+n)%m) { sum += (wins[cur] == 'P') ? 1 : -1; elem[rl] = {rl, &elem[rl], &elem[rl]}; add(bl[OFF+sum], &elem[rl]); used[cur] = true; if (sum > max) max = sum; ++rl; } int psum = 0; int cur = i%m; for (int j = 0; j < rl; ++j) { for (int id = cur; id < n && !checked[id]; id += m) { // przegrywa przed końcem cyklu int tl = a[id]; if (tl+psum < MAX_M && bl[OFF+tl+psum]) { min = std::min(min, ((long long)bl[OFF+tl+psum]->num-j)*n+id+1); } else { // dograj do końca cyklu tl -= sum-psum; // ile cykli musimy jeszcze rozegrać int cycles = 0; if (sum > 0 && tl > max) { cycles = (tl-max+sum-1)/sum; } tl -= cycles*sum; // gry = ile czekamy na kolejkę long long games = id+1; // + cykl dograny do końca games += ((long long)rl-j)*n; // + cykle które gramy całe games += ((long long)rl)*n*cycles; if (tl < MAX_M) { if (ab[OFF+tl]) { min = std::min(min, games+((long long)ab[OFF+tl]->num)*n); } else if (bl[OFF+tl]) { min = std::min(min, games+((long long)bl[OFF+tl]->num)*n); } } } checked[id] = true; } psum += (wins[cur] == 'P') ? 1 : -1; struct list* el = bl[OFF+psum]; pop(bl[OFF+psum]); add(ab[OFF+psum], el); cur = (cur+n)%m; } for (int j = max-rl; j <= max; ++j) { bl[OFF+j] = ab[OFF+j] = NULL; } } if (min == INF) { printf("-1\n"); } else { printf("%lld\n", min); } } |