#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PI; typedef long long LL; typedef double D; #define FI first #define SE second #define MP make_pair #define PB push_back #define R(I,N) for(int I=0;I<N;I++) #define F(I,A,B) for(int I=A;I<B;I++) #define FD(I,N) for(int I=N-1;I>=0;I--) #define make(A) scanf("%d",&A) #define make2(A,B) scanf("%d%d",&A,&B) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define db if(1)printf template<typename C> void MA(C& a,C b){if(a<b)a=b;} template<typename C> void MI(C& a,C b){if(a>b)a=b;} #define MAX 1001000 const LL inf = 2e18; int t[MAX],p[MAX],kie[MAX]; int n,m; char z[MAX]; vector<int> dd[MAX*2 + 100]; vector<int>* d = dd + MAX + 50; int spr(int war,int kt){ if(war > MAX || war < -MAX)return -1; auto pom = lower_bound(ALL(d[war]),kt); if(pom == d[war].end()) return -1; return *pom; } LL wyn[MAX]; main(){ make(n); R(i,n)make(t[i]); make(m); scanf("%s",z); int krok = n%m; int nc = __gcd(n,m); R(i,nc){ int sum = 0; int gd = i; int kt = 0; int mi = 1; do{ p[kt] = sum; kie[gd] = kt; sum += z[gd] == 'W'?1:-1; MI(mi,sum); d[sum].PB(kt); kt++; gd += krok; if(gd >= m)gd -= m; }while(i!=gd); for(int j = i; j < n;j+=nc){ int st = kie[j%m]; int szu = t[j] - p[st]; int res = spr(-szu,st); if(res != -1){ wyn[j] = (res - st) * 1ll * n + j; continue; } szu += sum; if(szu + mi <= 0){ wyn[j] = (*d[-szu].begin() + kt - st) * 1ll * n + j; }else if(sum < 0){ int obr = (szu + mi - sum - 1) / -sum; szu += obr * sum; wyn[j] = (*d[-szu].begin() + kt - st + obr *1ll* kt)*n + j; }else wyn[j] = inf; } while(SZ(d[mi])){ d[mi].clear(); mi++; } } LL wynik = *min_element(wyn,wyn+n); if(wynik == inf) puts("-1"); else printf("%lld\n",wynik+1); // R(i,n){ // if(wyn[i] == inf || wyn[i] > 10000000) // puts("-1"); // else // printf("%lld\n",wyn[i]+1); // } }
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 | #include<bits/stdc++.h> using namespace std; typedef pair<int,int> PI; typedef long long LL; typedef double D; #define FI first #define SE second #define MP make_pair #define PB push_back #define R(I,N) for(int I=0;I<N;I++) #define F(I,A,B) for(int I=A;I<B;I++) #define FD(I,N) for(int I=N-1;I>=0;I--) #define make(A) scanf("%d",&A) #define make2(A,B) scanf("%d%d",&A,&B) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define db if(1)printf template<typename C> void MA(C& a,C b){if(a<b)a=b;} template<typename C> void MI(C& a,C b){if(a>b)a=b;} #define MAX 1001000 const LL inf = 2e18; int t[MAX],p[MAX],kie[MAX]; int n,m; char z[MAX]; vector<int> dd[MAX*2 + 100]; vector<int>* d = dd + MAX + 50; int spr(int war,int kt){ if(war > MAX || war < -MAX)return -1; auto pom = lower_bound(ALL(d[war]),kt); if(pom == d[war].end()) return -1; return *pom; } LL wyn[MAX]; main(){ make(n); R(i,n)make(t[i]); make(m); scanf("%s",z); int krok = n%m; int nc = __gcd(n,m); R(i,nc){ int sum = 0; int gd = i; int kt = 0; int mi = 1; do{ p[kt] = sum; kie[gd] = kt; sum += z[gd] == 'W'?1:-1; MI(mi,sum); d[sum].PB(kt); kt++; gd += krok; if(gd >= m)gd -= m; }while(i!=gd); for(int j = i; j < n;j+=nc){ int st = kie[j%m]; int szu = t[j] - p[st]; int res = spr(-szu,st); if(res != -1){ wyn[j] = (res - st) * 1ll * n + j; continue; } szu += sum; if(szu + mi <= 0){ wyn[j] = (*d[-szu].begin() + kt - st) * 1ll * n + j; }else if(sum < 0){ int obr = (szu + mi - sum - 1) / -sum; szu += obr * sum; wyn[j] = (*d[-szu].begin() + kt - st + obr *1ll* kt)*n + j; }else wyn[j] = inf; } while(SZ(d[mi])){ d[mi].clear(); mi++; } } LL wynik = *min_element(wyn,wyn+n); if(wynik == inf) puts("-1"); else printf("%lld\n",wynik+1); // R(i,n){ // if(wyn[i] == inf || wyn[i] > 10000000) // puts("-1"); // else // printf("%lld\n",wyn[i]+1); // } } |