#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back #define inf 1000000009 #define infLL 1000000000000000023ll using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; inline int ceil2(int a){return 1<<((sizeof(int)<<3)-__builtin_clz(a));} int n,m,c,dc,skok,size,a[1000001],sc[1000001]; ll wynik=infLL; pii knc[1000001],kmc[1000001]; // first - ktory cykl | second - miejsce na cyklu char s[1000001]; void add(int *tree,int a,int x) { a+=size>>1; while (a) tree[a]=min(tree[a],x),a>>=1; } int min(int *tree,int a,int b,int nr=1,int z1=0,int z2=(size>>1)-1) { if (a==z1 && b==z2) return tree[nr]; int sr=(z1+z2)>>1,ret=inf; if (a<=sr) ret=min(ret,min(tree,a,min(b,sr),nr<<1,z1,sr)); if (b>sr) ret=min(ret,min(tree,max(a,sr+1),b,(nr<<1)+1,sr+1,z2)); return ret; } int wh(int *tree,int a,int b,int val,int nr=1,int z1=0,int z2=(size>>1)-1) { if (z1==z2) { if (tree[nr]<=val) return a; return -1; } int sr=(z1+z2)>>1; if (b<=sr) return wh(tree,a,b,val,nr<<1,z1,sr); if (a>sr) return wh(tree,a,b,val,(nr<<1)+1,sr+1,z2); int lewo=min(tree,a,sr,nr<<1,z1,sr); if (lewo<=val) return wh(tree,a,sr,val,nr<<1,z1,sr); return wh(tree,sr+1,b,val,(nr<<1)+1,sr+1,z2); } void _start(int a,int x) { kmc[a].e2=x; int nast=(a+n)%m; if (nast>=c) _start(nast,x+1); } int main() { scanf("%d",&n); REP(i,n) scanf("%d",&a[i]); scanf("%d\n",&m); gets(s); REP(i,m) s[i]=s[i]=='W'?1:-1; c=__gcd(n,m); dc=m/c; skok=n%m; REP(i,m) kmc[i].e1=i%c; REP(i,c) _start(i,0); REP(i,n) knc[i]=kmc[i%m]; size=ceil2(dc-1)<<1; int x[c][dc],spc[c][dc],tree[c][size]; pii pref[c][dc],suf[c][dc]; REP(i,m) x[kmc[i].e1][kmc[i].e2]=i; REP(i,c) REP(j,size) tree[i][j]=inf; REP(i,c) REP(j,dc) sc[i]+=s[x[i][j]],spc[i][j]=(j?spc[i][j-1]:0)+s[x[i][j]],add(tree[i],j,spc[i][j]); REP(i,c) REP(j,dc) if (!j || spc[i][j]<pref[i][j-1].e1) pref[i][j]=mp(spc[i][j],j); else pref[i][j]=pref[i][j-1]; REP(i,c) FORD(j,dc-1,0) if (j==dc-1 || spc[i][j]<=suf[i][j+1].e1) suf[i][j]=mp(spc[i][j],j); else suf[i][j]=suf[i][j+1]; REP(i,n) { int cykl=knc[i].e1,gdzie=knc[i].e2; pii minpcykl=mp(suf[cykl][gdzie].e1-(gdzie?spc[cykl][gdzie-1]:0),suf[cykl][gdzie].e2); pii minlcykl=gdzie?mp(sc[cykl]-(gdzie?spc[cykl][gdzie-1]:0)+pref[cykl][gdzie-1].e1,pref[cykl][gdzie-1].e2):mp(inf,inf); pii mincykl=minpcykl.e1==minlcykl.e1?minpcykl:min(minpcykl,minlcykl); if (a[i]+mincykl.e1>0 && sc[cykl]>=0) continue; int przejscia=sc[cykl]<0?(a[i]+mincykl.e1-1)/-sc[cykl]+1:0; if (przejscia<0 || a[i]+mincykl.e1<=0) przejscia=0; a[i]+=przejscia*sc[cykl]; if (minpcykl.e1<=-a[i]) { int ktory=wh(tree[cykl],gdzie,dc-1,-a[i]+(gdzie?spc[cykl][gdzie-1]:0)); wynik=min(wynik,(ll)n*((ll)przejscia*dc+ktory-gdzie)+i); } else { int ktory=wh(tree[cykl],0,gdzie-1,-a[i]-sc[cykl]+spc[cykl][gdzie-1]); wynik=min(wynik,(ll)n*((ll)przejscia*dc+dc+ktory-gdzie)+i); } } assert(wynik>=0); if (wynik==infLL) puts("-1"); else printf("%lld\n",wynik+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 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<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back #define inf 1000000009 #define infLL 1000000000000000023ll using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; inline int ceil2(int a){return 1<<((sizeof(int)<<3)-__builtin_clz(a));} int n,m,c,dc,skok,size,a[1000001],sc[1000001]; ll wynik=infLL; pii knc[1000001],kmc[1000001]; // first - ktory cykl | second - miejsce na cyklu char s[1000001]; void add(int *tree,int a,int x) { a+=size>>1; while (a) tree[a]=min(tree[a],x),a>>=1; } int min(int *tree,int a,int b,int nr=1,int z1=0,int z2=(size>>1)-1) { if (a==z1 && b==z2) return tree[nr]; int sr=(z1+z2)>>1,ret=inf; if (a<=sr) ret=min(ret,min(tree,a,min(b,sr),nr<<1,z1,sr)); if (b>sr) ret=min(ret,min(tree,max(a,sr+1),b,(nr<<1)+1,sr+1,z2)); return ret; } int wh(int *tree,int a,int b,int val,int nr=1,int z1=0,int z2=(size>>1)-1) { if (z1==z2) { if (tree[nr]<=val) return a; return -1; } int sr=(z1+z2)>>1; if (b<=sr) return wh(tree,a,b,val,nr<<1,z1,sr); if (a>sr) return wh(tree,a,b,val,(nr<<1)+1,sr+1,z2); int lewo=min(tree,a,sr,nr<<1,z1,sr); if (lewo<=val) return wh(tree,a,sr,val,nr<<1,z1,sr); return wh(tree,sr+1,b,val,(nr<<1)+1,sr+1,z2); } void _start(int a,int x) { kmc[a].e2=x; int nast=(a+n)%m; if (nast>=c) _start(nast,x+1); } int main() { scanf("%d",&n); REP(i,n) scanf("%d",&a[i]); scanf("%d\n",&m); gets(s); REP(i,m) s[i]=s[i]=='W'?1:-1; c=__gcd(n,m); dc=m/c; skok=n%m; REP(i,m) kmc[i].e1=i%c; REP(i,c) _start(i,0); REP(i,n) knc[i]=kmc[i%m]; size=ceil2(dc-1)<<1; int x[c][dc],spc[c][dc],tree[c][size]; pii pref[c][dc],suf[c][dc]; REP(i,m) x[kmc[i].e1][kmc[i].e2]=i; REP(i,c) REP(j,size) tree[i][j]=inf; REP(i,c) REP(j,dc) sc[i]+=s[x[i][j]],spc[i][j]=(j?spc[i][j-1]:0)+s[x[i][j]],add(tree[i],j,spc[i][j]); REP(i,c) REP(j,dc) if (!j || spc[i][j]<pref[i][j-1].e1) pref[i][j]=mp(spc[i][j],j); else pref[i][j]=pref[i][j-1]; REP(i,c) FORD(j,dc-1,0) if (j==dc-1 || spc[i][j]<=suf[i][j+1].e1) suf[i][j]=mp(spc[i][j],j); else suf[i][j]=suf[i][j+1]; REP(i,n) { int cykl=knc[i].e1,gdzie=knc[i].e2; pii minpcykl=mp(suf[cykl][gdzie].e1-(gdzie?spc[cykl][gdzie-1]:0),suf[cykl][gdzie].e2); pii minlcykl=gdzie?mp(sc[cykl]-(gdzie?spc[cykl][gdzie-1]:0)+pref[cykl][gdzie-1].e1,pref[cykl][gdzie-1].e2):mp(inf,inf); pii mincykl=minpcykl.e1==minlcykl.e1?minpcykl:min(minpcykl,minlcykl); if (a[i]+mincykl.e1>0 && sc[cykl]>=0) continue; int przejscia=sc[cykl]<0?(a[i]+mincykl.e1-1)/-sc[cykl]+1:0; if (przejscia<0 || a[i]+mincykl.e1<=0) przejscia=0; a[i]+=przejscia*sc[cykl]; if (minpcykl.e1<=-a[i]) { int ktory=wh(tree[cykl],gdzie,dc-1,-a[i]+(gdzie?spc[cykl][gdzie-1]:0)); wynik=min(wynik,(ll)n*((ll)przejscia*dc+ktory-gdzie)+i); } else { int ktory=wh(tree[cykl],0,gdzie-1,-a[i]-sc[cykl]+spc[cykl][gdzie-1]); wynik=min(wynik,(ll)n*((ll)przejscia*dc+dc+ktory-gdzie)+i); } } assert(wynik>=0); if (wynik==infLL) puts("-1"); else printf("%lld\n",wynik+1); } |