#include<iostream> #include<vector> #include<algorithm> //#include<assert.h> using namespace std; int n; // liczba kolegow int A[1000000+10]; // pieniadze kolegow int m; // cykl automatu char T[1000000+10]; // zachowanie automatu int S[2000000+10]; int pos[2000000+10]; int Next[2000000+10]; // next[i]=j wtw S[i] > S[j] i j jest najmniejsze takie w przedziale [i,i+k], jesli nie ma to j = i int Min[1000000+10]; // wskazuje pozycje wartosci minimalnej w [i,i+k] long long play[1000000+10]; int GCD(int n,int m) { int t; if (m>n) {t=m; m=n; n=t;} while (m!=0) {t=n%m; n=m; m=t;} return n; } /* GCD */ int minValZigZag; // minimalna wartosc zygzaka int maxValZigZag; // maksymalna wartosc zygzaka // buduje zygzag w przedziale [0,2k] // startujac od chlopca p, 0<=p<n void buildZigZag(int k,int p){ S[0] = 0; p = p%m; minValZigZag = maxValZigZag = 0; //! pos[0] jest niezdefiniowane, nie uzywac tej wartosci!!! for(int i=1;i<=2*k;++i){ S[i] = S[i-1] + (T[p]=='W'?1:-1); if(S[i] < minValZigZag) minValZigZag = S[i]; if(S[i] > maxValZigZag) maxValZigZag = S[i]; pos[i] = p; // wskazuje, ktorego stanu automatu dotyczy wpis S[i] p = (p+n)%m; } } // buduje funkcje Next w przedziale [0,2k] void buildNext(int k){ for(int i=0;i<=2*k;++i) Next[i]=i; vector<int> stack(0); stack.push_back(0); for(int i = 1; i<=2*k;++i){ // S[i] - aktualna wysokosc while(!stack.empty() && S[stack.back()]>S[i]) { Next[stack.back()] = i; stack.pop_back(); } stack.push_back(i); } } // buduje funkcje Min w przedziale [0,k] void buildMin(int k){ int p = 0; // potencjalna pozycja wskazujaca wartosc minimalna for(int j = 0;j<=k;++j){ while (Next[p]!=p && Next[p] <= k+j) p = Next[p]; Min[j] = p; } } struct revZigZag{ int N; int L,R; vector<vector<int>> Tab; // przechowuje wartosci w przedziale [l,r], l moze byc ujemne revZigZag(int l,int r) : N(r-l+1), L(l), R(r), Tab(N){ for(int i=0;i<N;++i) Tab[i] = vector<int>(0); } void put(int pos,int val){ Tab[pos-L].push_back(val); } void build(int k){ for(int i=0;i<=2*k;++i) { /// assert(S[i] >=L and S[i] <=R); put(S[i],i); } } // znajduje pierwsza pozycje pos w Tab[val-L] taka, ze pos>=p int getFirstPos(int val, int p){ /// assert(val-L >= 0); auto ptr = lower_bound(Tab[val-L].begin(),Tab[val-L].end(),p); if (ptr == Tab[val-L].end()) return -1; else return *ptr; //~ for(int pos : Tab[val-L]) if(pos >= p) return pos; //~ return -1; } }; // sprawdza, czy po t krokach faktycznie nastapi przegrana int check(long long t){ if(t==-1) return 1; t--; int k = m / GCD(n,m); int boy = t%n; // ten chlopak ma przegrac buildZigZag(k,boy); t-=boy; t/=n; long long r = A[boy] + t/k * S[k]; t = t%(k); return r + S[t+1] == 0; } int main(){ cin >> n; for(int i=0;i<n;++i) cin>>A[i]; cin >> m; cin >> T; int k = m / GCD(n,m); // powtarzalnosc gry for(int boy = 0;boy<n;++boy) if(play[boy]==0){ buildZigZag(k,boy); revZigZag jumps(minValZigZag,maxValZigZag); jumps.build(k); // S[k] wskazuje, czy po pelnym cyku jest przyrost, czy spadek (jesli < 0 to po pewnym czasie bedzie przegrana) int earn = S[k]; // w kazdym przedziale [i,i+k] znalezc minimalna wartosc, i=0,...,k-1 // najpierw zbuduj funkcje Next buildNext(k); // za pomoca Next oblicz Min buildMin(k); // obliczyc, ktore chlopaki graja na pozycji pos[i] for(int i=1;i<=k;++i){ for(int b = pos[i]; b<n;b+=m){ // b - numer chlopaka, ktoremu odpowiada ciag zaczynajacy sie od i-1 if(play[b]!=0) continue; int minpos = Min[i-1]; // pozycja minimalnej wartosci int minval = S[minpos]-S[i-1]; // maksymalny spadek wartosci, minval <=0 if(A[b]+minval > 0 && earn >= 0 ) play[b] = -1; // nigdy nie przegra else{ // jest przegrana, obliczyc kiedy long long r = 1LL*(A[b]+minval-earn-1)/(-earn); if(r<0)r=0; if(earn >=0 ) r = 0; // A[b]+earn*r - tyle trzeba sie jeszcze pozbyc, A[b]+earn*r + minval <= 0 long long w = r*earn+A[b]; // w + minval <= 0, w >=0 // patrzymy na poziom S[i-1]-w int pos = jumps.getFirstPos(S[i-1]-w,i-1); if(pos<0) play[b]=-1; else{ /// assert(pos>=0); play[b] = b+1 + r*n*k + 1LL*(pos-i)*n; } } } } } long long v=-1; int i=0,j=0; for(;i<n;++i)if(play[i]>0){v=play[i]; j=i;break;} for(;i<n;++i)if(play[i]>0 && play[i]<v)v=play[j=i]; printf("%lld\n",v); /// assert(check(v)); 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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | #include<iostream> #include<vector> #include<algorithm> //#include<assert.h> using namespace std; int n; // liczba kolegow int A[1000000+10]; // pieniadze kolegow int m; // cykl automatu char T[1000000+10]; // zachowanie automatu int S[2000000+10]; int pos[2000000+10]; int Next[2000000+10]; // next[i]=j wtw S[i] > S[j] i j jest najmniejsze takie w przedziale [i,i+k], jesli nie ma to j = i int Min[1000000+10]; // wskazuje pozycje wartosci minimalnej w [i,i+k] long long play[1000000+10]; int GCD(int n,int m) { int t; if (m>n) {t=m; m=n; n=t;} while (m!=0) {t=n%m; n=m; m=t;} return n; } /* GCD */ int minValZigZag; // minimalna wartosc zygzaka int maxValZigZag; // maksymalna wartosc zygzaka // buduje zygzag w przedziale [0,2k] // startujac od chlopca p, 0<=p<n void buildZigZag(int k,int p){ S[0] = 0; p = p%m; minValZigZag = maxValZigZag = 0; //! pos[0] jest niezdefiniowane, nie uzywac tej wartosci!!! for(int i=1;i<=2*k;++i){ S[i] = S[i-1] + (T[p]=='W'?1:-1); if(S[i] < minValZigZag) minValZigZag = S[i]; if(S[i] > maxValZigZag) maxValZigZag = S[i]; pos[i] = p; // wskazuje, ktorego stanu automatu dotyczy wpis S[i] p = (p+n)%m; } } // buduje funkcje Next w przedziale [0,2k] void buildNext(int k){ for(int i=0;i<=2*k;++i) Next[i]=i; vector<int> stack(0); stack.push_back(0); for(int i = 1; i<=2*k;++i){ // S[i] - aktualna wysokosc while(!stack.empty() && S[stack.back()]>S[i]) { Next[stack.back()] = i; stack.pop_back(); } stack.push_back(i); } } // buduje funkcje Min w przedziale [0,k] void buildMin(int k){ int p = 0; // potencjalna pozycja wskazujaca wartosc minimalna for(int j = 0;j<=k;++j){ while (Next[p]!=p && Next[p] <= k+j) p = Next[p]; Min[j] = p; } } struct revZigZag{ int N; int L,R; vector<vector<int>> Tab; // przechowuje wartosci w przedziale [l,r], l moze byc ujemne revZigZag(int l,int r) : N(r-l+1), L(l), R(r), Tab(N){ for(int i=0;i<N;++i) Tab[i] = vector<int>(0); } void put(int pos,int val){ Tab[pos-L].push_back(val); } void build(int k){ for(int i=0;i<=2*k;++i) { /// assert(S[i] >=L and S[i] <=R); put(S[i],i); } } // znajduje pierwsza pozycje pos w Tab[val-L] taka, ze pos>=p int getFirstPos(int val, int p){ /// assert(val-L >= 0); auto ptr = lower_bound(Tab[val-L].begin(),Tab[val-L].end(),p); if (ptr == Tab[val-L].end()) return -1; else return *ptr; //~ for(int pos : Tab[val-L]) if(pos >= p) return pos; //~ return -1; } }; // sprawdza, czy po t krokach faktycznie nastapi przegrana int check(long long t){ if(t==-1) return 1; t--; int k = m / GCD(n,m); int boy = t%n; // ten chlopak ma przegrac buildZigZag(k,boy); t-=boy; t/=n; long long r = A[boy] + t/k * S[k]; t = t%(k); return r + S[t+1] == 0; } int main(){ cin >> n; for(int i=0;i<n;++i) cin>>A[i]; cin >> m; cin >> T; int k = m / GCD(n,m); // powtarzalnosc gry for(int boy = 0;boy<n;++boy) if(play[boy]==0){ buildZigZag(k,boy); revZigZag jumps(minValZigZag,maxValZigZag); jumps.build(k); // S[k] wskazuje, czy po pelnym cyku jest przyrost, czy spadek (jesli < 0 to po pewnym czasie bedzie przegrana) int earn = S[k]; // w kazdym przedziale [i,i+k] znalezc minimalna wartosc, i=0,...,k-1 // najpierw zbuduj funkcje Next buildNext(k); // za pomoca Next oblicz Min buildMin(k); // obliczyc, ktore chlopaki graja na pozycji pos[i] for(int i=1;i<=k;++i){ for(int b = pos[i]; b<n;b+=m){ // b - numer chlopaka, ktoremu odpowiada ciag zaczynajacy sie od i-1 if(play[b]!=0) continue; int minpos = Min[i-1]; // pozycja minimalnej wartosci int minval = S[minpos]-S[i-1]; // maksymalny spadek wartosci, minval <=0 if(A[b]+minval > 0 && earn >= 0 ) play[b] = -1; // nigdy nie przegra else{ // jest przegrana, obliczyc kiedy long long r = 1LL*(A[b]+minval-earn-1)/(-earn); if(r<0)r=0; if(earn >=0 ) r = 0; // A[b]+earn*r - tyle trzeba sie jeszcze pozbyc, A[b]+earn*r + minval <= 0 long long w = r*earn+A[b]; // w + minval <= 0, w >=0 // patrzymy na poziom S[i-1]-w int pos = jumps.getFirstPos(S[i-1]-w,i-1); if(pos<0) play[b]=-1; else{ /// assert(pos>=0); play[b] = b+1 + r*n*k + 1LL*(pos-i)*n; } } } } } long long v=-1; int i=0,j=0; for(;i<n;++i)if(play[i]>0){v=play[i]; j=i;break;} for(;i<n;++i)if(play[i]>0 && play[i]<v)v=play[j=i]; printf("%lld\n",v); /// assert(check(v)); return 0; } |