#include<iostream> #include<vector> #define PII pair<int,int> #define INF 2000000000000000000LL #define mp make_pair #define st first #define nd second #define pb push_back #define LL long long using namespace std; int kasa[1000000]; PII gdzie[1000000]; LL wynik[1000000]; vector<int>chlopcy[1000000]; const int p1=1024*2048; int drz[p1*2]; void insert(int x,int a){ x+=p1-1; drz[x]=a; x=(x-1)/2; while(1){ drz[x]=max(drz[2*x+1],drz[2*x+2]); if(x==0)return; x=(x-1)/2; } } int pos(int gran){ int x=0; if(gran>drz[0])return -1; while(x<p1-1){ if(drz[2*x+1]>=gran)x=2*x+1; else x=2*x+2; } return x-p1+1; } int maks(int a,int b){ a+=p1-1; b+=p1-1; int res=max(drz[a],drz[b]); while((a-1)/2!=(b-1)/2){ if(a%2==1)res=max(res,drz[a+1]); if(b%2==0)res=max(res,drz[b-1]); a=(a-1)/2; b=(b-1)/2; } return res; } string gra; vector<vector<int> >cykl; int wart(char c){ if(c=='W')return 1; else return -1; } void licz(int x){ int n=cykl[x].size(); /*cout<<"licz\n"; for(int i=0;i<n;i++)cout<<wart(gra[cykl[x][i]])<<" "; cout<<"\n";*/ for(int i=0;i<2*n;i++)insert(i,-1000000000); insert(0,-wart(gra[cykl[x][0]])); for(int i=1;i<n;i++)insert(i,-wart(gra[cykl[x][i]])+drz[p1-2+i]); int poprawka=0,suma=drz[p1-1+n-1]; for(int i=0;i<n;i++){ int najw=maks(i,i+n-1)+poprawka,tury; /*cout<<"najw suma pop "<<najw<<" "<<suma<<" "<<poprawka<<"\n"; for(int j=0;j<n;j++)cout<<drz[p1-1+i+j]<<" "; cout<<"\n";*/ for(int j=0;j<chlopcy[cykl[x][i]].size();j++){ tury=0; int kwota=kasa[chlopcy[cykl[x][i]][j]]; //cout<<"kwota "<<kwota<<"\n"; if(kwota>najw&&suma>0){ tury=(kwota-najw+suma-1)/suma; } int granica=kwota-tury*suma; int p=pos(granica-poprawka); if(p!=-1)p-=i; if(p>=n)p=-1; //cout<<"p tury "<<p<<" "<<tury<<"\n"; wynik[chlopcy[cykl[x][i]][j]]=((p==-1)?INF:((LL)tury*n+p)); if(granica==0&&p!=-1)wynik[chlopcy[cykl[x][i]][j]]--; //cout<<wynik[chlopcy[cykl[x][i]][j]]<<"\n"; } poprawka+=wart(gra[cykl[x][i]]); insert(i,-1000000000); insert(i+n,drz[p1-1+i+n-1]-wart(gra[cykl[x][i]])); } } int m,nn; LL koniec(int nr){ if(wynik[nr]==INF)return INF; return (LL)nr+1+wynik[nr]*nn; } bool odw[1000000]; main(){ ios_base::sync_with_stdio(0); int n; cin>>n; nn=n; for(int i=0;i<n;i++)cin>>kasa[i]; cin>>m; for(int i=0;i<n;i++)chlopcy[i%m].pb(i); cin>>gra; for(int i=0;i<m;i++){ if(odw[i])continue; vector<int>tmp; gdzie[i]=mp(cykl.size(),tmp.size()); tmp.pb(i); odw[i]=1; int x=(i+n)%m; while(x!=i){ gdzie[x]=mp(cykl.size(),tmp.size()); tmp.pb(x); odw[x]=1; x=(x+n)%m; } cykl.pb(tmp); } for(int i=0;i<cykl.size();i++)licz(i); LL res=INF; for(int i=0;i<n;i++){ LL akt=koniec(i); if(res>akt)res=akt; } if(res==INF)cout<<"-1\n"; else cout<<res<<"\n"; }
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 | #include<iostream> #include<vector> #define PII pair<int,int> #define INF 2000000000000000000LL #define mp make_pair #define st first #define nd second #define pb push_back #define LL long long using namespace std; int kasa[1000000]; PII gdzie[1000000]; LL wynik[1000000]; vector<int>chlopcy[1000000]; const int p1=1024*2048; int drz[p1*2]; void insert(int x,int a){ x+=p1-1; drz[x]=a; x=(x-1)/2; while(1){ drz[x]=max(drz[2*x+1],drz[2*x+2]); if(x==0)return; x=(x-1)/2; } } int pos(int gran){ int x=0; if(gran>drz[0])return -1; while(x<p1-1){ if(drz[2*x+1]>=gran)x=2*x+1; else x=2*x+2; } return x-p1+1; } int maks(int a,int b){ a+=p1-1; b+=p1-1; int res=max(drz[a],drz[b]); while((a-1)/2!=(b-1)/2){ if(a%2==1)res=max(res,drz[a+1]); if(b%2==0)res=max(res,drz[b-1]); a=(a-1)/2; b=(b-1)/2; } return res; } string gra; vector<vector<int> >cykl; int wart(char c){ if(c=='W')return 1; else return -1; } void licz(int x){ int n=cykl[x].size(); /*cout<<"licz\n"; for(int i=0;i<n;i++)cout<<wart(gra[cykl[x][i]])<<" "; cout<<"\n";*/ for(int i=0;i<2*n;i++)insert(i,-1000000000); insert(0,-wart(gra[cykl[x][0]])); for(int i=1;i<n;i++)insert(i,-wart(gra[cykl[x][i]])+drz[p1-2+i]); int poprawka=0,suma=drz[p1-1+n-1]; for(int i=0;i<n;i++){ int najw=maks(i,i+n-1)+poprawka,tury; /*cout<<"najw suma pop "<<najw<<" "<<suma<<" "<<poprawka<<"\n"; for(int j=0;j<n;j++)cout<<drz[p1-1+i+j]<<" "; cout<<"\n";*/ for(int j=0;j<chlopcy[cykl[x][i]].size();j++){ tury=0; int kwota=kasa[chlopcy[cykl[x][i]][j]]; //cout<<"kwota "<<kwota<<"\n"; if(kwota>najw&&suma>0){ tury=(kwota-najw+suma-1)/suma; } int granica=kwota-tury*suma; int p=pos(granica-poprawka); if(p!=-1)p-=i; if(p>=n)p=-1; //cout<<"p tury "<<p<<" "<<tury<<"\n"; wynik[chlopcy[cykl[x][i]][j]]=((p==-1)?INF:((LL)tury*n+p)); if(granica==0&&p!=-1)wynik[chlopcy[cykl[x][i]][j]]--; //cout<<wynik[chlopcy[cykl[x][i]][j]]<<"\n"; } poprawka+=wart(gra[cykl[x][i]]); insert(i,-1000000000); insert(i+n,drz[p1-1+i+n-1]-wart(gra[cykl[x][i]])); } } int m,nn; LL koniec(int nr){ if(wynik[nr]==INF)return INF; return (LL)nr+1+wynik[nr]*nn; } bool odw[1000000]; main(){ ios_base::sync_with_stdio(0); int n; cin>>n; nn=n; for(int i=0;i<n;i++)cin>>kasa[i]; cin>>m; for(int i=0;i<n;i++)chlopcy[i%m].pb(i); cin>>gra; for(int i=0;i<m;i++){ if(odw[i])continue; vector<int>tmp; gdzie[i]=mp(cykl.size(),tmp.size()); tmp.pb(i); odw[i]=1; int x=(i+n)%m; while(x!=i){ gdzie[x]=mp(cykl.size(),tmp.size()); tmp.pb(x); odw[x]=1; x=(x+n)%m; } cykl.pb(tmp); } for(int i=0;i<cykl.size();i++)licz(i); LL res=INF; for(int i=0;i<n;i++){ LL akt=koniec(i); if(res>akt)res=akt; } if(res==INF)cout<<"-1\n"; else cout<<res<<"\n"; } |