#include<iostream> #include <algorithm> using namespace std; const long long int NN = 1000 * 1000 + 7, MAXX = 9223372036854775807LL; long long int tab[NN], gra[NN], kol[NN], ch[NN], w[NN], m, n, d, a, c, s, wyn; char cc; long long int nwd(long long int i,long long int j) { long long int k; while (i > 0) { k = i; i = j % i; j = k; } return j; } long long int i, j; int main() { ios_base::sync_with_stdio(0); cin >> n; for(i = 0; i < n; i++) { cin >> ch[i]; gra[i] = -1; } cin >> m; for (i = 0; i < m; i++) { cin >> cc; if (cc=='W') w[i] = 1; else w[i] = -1; } d = nwd(m, n); //cout << "MAXX: " << MAXX << "\n"; //cout << "d: " << d << "\n"; wyn = MAXX; //cout << "wyn: " << wyn << "\n"; for (c = 0; c < d; c++) { j = c; s = 0; a = -1; for (i = 0; i < m / d; i++) { kol[m / d - 1 - i] = j; j = (j + n) % m; } /* for (j = 0; j < m / d; j++) cout << kol[j] << " "; cout << "\n"; */ for (i = 0; i < m / d; i++) { s = s + w[kol[i]]; // cout << "s: " << s << "\n"; if (w[kol[i]] < 0) { a++; tab[a] = i; } else if (a >= 0) a--; /* for (j = 0; j <= a ; j++) cout << tab[j] << " "; cout << "\n"; */ for (j = kol[i]; j < n; j = j + m) { if (ch[j] > a + 1) { ch[j] = ch[j] + s; gra[j] = i; } else { gra[j] = i - tab[a - ch[j] + 1]; ch[j] = 0; } // cout << "j: " << j << " " << ch[j] << " " << gra[j] << "\n"; } } for (i = c; i < n; i = i + d) { if ((ch[i] > a + 1) && (s >= 0)) { gra[i] = -1; ch[i] = 0; } if (ch[i] > 0) { if (ch[i] > a + 1) { j = ((ch[i] - a - 2) / ((-1)*s)) + 1; gra[i] = gra[i] + (m / d) * j; ch[i] = ch[i] + s * j; } gra[i] = gra[i] + (m / d) - tab[a + 1 - ch[i]]; } if (gra[i] != (-1)) wyn = min(wyn, gra[i] * n + i + 1); /* cout << "i: " << i << " " << gra[i] << " " << gra[i] * n + i + 1 << "\n"; cout << "wyn: " << wyn << "\n";*/ } } if (wyn==MAXX) cout << -1; else cout << 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 | #include<iostream> #include <algorithm> using namespace std; const long long int NN = 1000 * 1000 + 7, MAXX = 9223372036854775807LL; long long int tab[NN], gra[NN], kol[NN], ch[NN], w[NN], m, n, d, a, c, s, wyn; char cc; long long int nwd(long long int i,long long int j) { long long int k; while (i > 0) { k = i; i = j % i; j = k; } return j; } long long int i, j; int main() { ios_base::sync_with_stdio(0); cin >> n; for(i = 0; i < n; i++) { cin >> ch[i]; gra[i] = -1; } cin >> m; for (i = 0; i < m; i++) { cin >> cc; if (cc=='W') w[i] = 1; else w[i] = -1; } d = nwd(m, n); //cout << "MAXX: " << MAXX << "\n"; //cout << "d: " << d << "\n"; wyn = MAXX; //cout << "wyn: " << wyn << "\n"; for (c = 0; c < d; c++) { j = c; s = 0; a = -1; for (i = 0; i < m / d; i++) { kol[m / d - 1 - i] = j; j = (j + n) % m; } /* for (j = 0; j < m / d; j++) cout << kol[j] << " "; cout << "\n"; */ for (i = 0; i < m / d; i++) { s = s + w[kol[i]]; // cout << "s: " << s << "\n"; if (w[kol[i]] < 0) { a++; tab[a] = i; } else if (a >= 0) a--; /* for (j = 0; j <= a ; j++) cout << tab[j] << " "; cout << "\n"; */ for (j = kol[i]; j < n; j = j + m) { if (ch[j] > a + 1) { ch[j] = ch[j] + s; gra[j] = i; } else { gra[j] = i - tab[a - ch[j] + 1]; ch[j] = 0; } // cout << "j: " << j << " " << ch[j] << " " << gra[j] << "\n"; } } for (i = c; i < n; i = i + d) { if ((ch[i] > a + 1) && (s >= 0)) { gra[i] = -1; ch[i] = 0; } if (ch[i] > 0) { if (ch[i] > a + 1) { j = ((ch[i] - a - 2) / ((-1)*s)) + 1; gra[i] = gra[i] + (m / d) * j; ch[i] = ch[i] + s * j; } gra[i] = gra[i] + (m / d) - tab[a + 1 - ch[i]]; } if (gra[i] != (-1)) wyn = min(wyn, gra[i] * n + i + 1); /* cout << "i: " << i << " " << gra[i] << " " << gra[i] * n + i + 1 << "\n"; cout << "wyn: " << wyn << "\n";*/ } } if (wyn==MAXX) cout << -1; else cout << wyn; return 0; } |