#include <iostream> #include <string> #include <queue> #include <algorithm> #include <list> using namespace std; const int N = 2000000; list<int> pos[2 * N + 1]; queue<int> cleaner; list<int> cykl_l; queue<int> indexy; long long n, m; int T[1000001]; int NWD(int a, int b) { if (!b) return a; return NWD(b, a % b); } int main() { ios_base::sync_with_stdio(0); string P; cin >> n; for (int i = 0; i < n; i++) { cin >> T[i]; } cin >> m >> P; // cout << n << " " << m << endl; int nwd = NWD(n, m); long long best = 1000000000000000000; for (int i = 0; i < nwd; i++) { string cykl; int stan = 0; for (int j = 0; j < m / nwd; j++) { cykl = cykl + P[(j * n + i) % m]; indexy.push((j * n + i) % m); if (P[(j * n + i) % m] == 'W') { stan++; } else { stan--; } pos[N + stan].push_back(j); // cout << "ZNAK " << j * nwd + i << " " << P[(j * n + i) % m] << " STAN " << stan << endl; cleaner.push(N + stan); while (!cykl_l.empty() && cykl_l.back() > stan) { cykl_l.pop_back(); } cykl_l.push_back(stan); } // cout << endl << cykl << " " << cykl_l.front() << " " << stan << endl << endl; int suma_cyklu = stan; long long wynik = best; int pref = 0; int k = i; int x = 0; while (!indexy.empty()) { k = indexy.front(); indexy.pop(); // sprawdz identyczne cykle for (int l = k; l < n; l += m) { // cout << "KOLES " << l << endl; // cout << T[l] << " " << cykl_l.front() - pref << " " << suma_cyklu << endl; if (!pos[N - T[l] + pref].empty()) { wynik = (pos[N - T[l] + pref].front() - x) * n + l; // cout << "SZYBKO KONCZY " << wynik << endl; } else if (suma_cyklu < 0) { int numer_cyklu = (T[l] + cykl_l.front() - pref) / -suma_cyklu + ((T[l] + cykl_l.front() - pref) % -suma_cyklu != 0); // cout << "KONCZY W CYKLU " << numer_cyklu << endl; // cout << "SZUKAMY " << numer_cyklu * -suma_cyklu - T[l] + pref << endl; // cout << "JEST NA POZYCJI " << pos[N - numer_cyklu * suma_cyklu - T[l] + pref].front() << " - " << x << endl; wynik = numer_cyklu * n / nwd * m + (pos[N - numer_cyklu * suma_cyklu - T[l] + pref].front() - x) * n + l; // cout << "W KOLEJCE " << wynik << endl; } best = min(wynik, best); } if (cykl[x] == 'W') { pref++; } else { pref--; } pos[N + pref].pop_front(); pos[N + pref + suma_cyklu].push_back(m / nwd + x); cleaner.push(N + pref + suma_cyklu); if (pref == cykl_l.front()) { cykl_l.pop_front(); } while (!cykl_l.empty() && cykl_l.back() > pref + suma_cyklu) { cykl_l.pop_back(); } cykl_l.push_back(pref + suma_cyklu); x++; } while (!cleaner.empty()) { while (!pos[cleaner.front()].empty()) { pos[cleaner.front()].pop_front(); } cleaner.pop(); } while (!cykl_l.empty()) { cykl_l.pop_back(); } while (!indexy.empty()) { indexy.pop(); } } if (best == 1000000000000000000) { cout << -1 << endl; } else { cout << best + 1 << endl; } 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 | #include <iostream> #include <string> #include <queue> #include <algorithm> #include <list> using namespace std; const int N = 2000000; list<int> pos[2 * N + 1]; queue<int> cleaner; list<int> cykl_l; queue<int> indexy; long long n, m; int T[1000001]; int NWD(int a, int b) { if (!b) return a; return NWD(b, a % b); } int main() { ios_base::sync_with_stdio(0); string P; cin >> n; for (int i = 0; i < n; i++) { cin >> T[i]; } cin >> m >> P; // cout << n << " " << m << endl; int nwd = NWD(n, m); long long best = 1000000000000000000; for (int i = 0; i < nwd; i++) { string cykl; int stan = 0; for (int j = 0; j < m / nwd; j++) { cykl = cykl + P[(j * n + i) % m]; indexy.push((j * n + i) % m); if (P[(j * n + i) % m] == 'W') { stan++; } else { stan--; } pos[N + stan].push_back(j); // cout << "ZNAK " << j * nwd + i << " " << P[(j * n + i) % m] << " STAN " << stan << endl; cleaner.push(N + stan); while (!cykl_l.empty() && cykl_l.back() > stan) { cykl_l.pop_back(); } cykl_l.push_back(stan); } // cout << endl << cykl << " " << cykl_l.front() << " " << stan << endl << endl; int suma_cyklu = stan; long long wynik = best; int pref = 0; int k = i; int x = 0; while (!indexy.empty()) { k = indexy.front(); indexy.pop(); // sprawdz identyczne cykle for (int l = k; l < n; l += m) { // cout << "KOLES " << l << endl; // cout << T[l] << " " << cykl_l.front() - pref << " " << suma_cyklu << endl; if (!pos[N - T[l] + pref].empty()) { wynik = (pos[N - T[l] + pref].front() - x) * n + l; // cout << "SZYBKO KONCZY " << wynik << endl; } else if (suma_cyklu < 0) { int numer_cyklu = (T[l] + cykl_l.front() - pref) / -suma_cyklu + ((T[l] + cykl_l.front() - pref) % -suma_cyklu != 0); // cout << "KONCZY W CYKLU " << numer_cyklu << endl; // cout << "SZUKAMY " << numer_cyklu * -suma_cyklu - T[l] + pref << endl; // cout << "JEST NA POZYCJI " << pos[N - numer_cyklu * suma_cyklu - T[l] + pref].front() << " - " << x << endl; wynik = numer_cyklu * n / nwd * m + (pos[N - numer_cyklu * suma_cyklu - T[l] + pref].front() - x) * n + l; // cout << "W KOLEJCE " << wynik << endl; } best = min(wynik, best); } if (cykl[x] == 'W') { pref++; } else { pref--; } pos[N + pref].pop_front(); pos[N + pref + suma_cyklu].push_back(m / nwd + x); cleaner.push(N + pref + suma_cyklu); if (pref == cykl_l.front()) { cykl_l.pop_front(); } while (!cykl_l.empty() && cykl_l.back() > pref + suma_cyklu) { cykl_l.pop_back(); } cykl_l.push_back(pref + suma_cyklu); x++; } while (!cleaner.empty()) { while (!pos[cleaner.front()].empty()) { pos[cleaner.front()].pop_front(); } cleaner.pop(); } while (!cykl_l.empty()) { cykl_l.pop_back(); } while (!indexy.empty()) { indexy.pop(); } } if (best == 1000000000000000000) { cout << -1 << endl; } else { cout << best + 1 << endl; } return 0; } |