Submission #1087424

#TimeUsernameProblemLanguageResultExecution timeMemory
1087424m5588ohammedRPS string (innopolis2021_final_C)C++14
100 / 100
55 ms29416 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long #define mod 998244353 int PP[500002],RP[500002],SP[500002],ans[500002],k1,k2; int PS[500002],RS[500002],SS[500002]; char P,S,R; string s; int n,d; void ers(){ k1=n+1; k2=-1; for(int i=1;i<=n+1;i++) PP[i]=RP[i]=SP[i]=PS[i]=RS[i]=SS[i]=0; return; } void ERS(){ for(int i=1;i<=n+1;i++) PP[i]=RP[i]=SP[i]=ans[i]=0; return; } void type1(int i){ if(RP[i]>0&&PP[i]>0){ if(RS[i]>0&&PS[i]>0) ans[i]=1; if(RS[i]==0) ans[i]=1; } if(RP[i]==0){ if(RS[i]>0&&PS[i]>0) ans[i]=1; if(RS[i]==0) ans[i]=1; } return; } bool left(int i){ if(RP[i]==i-1&&i!=1) return 0; if(i==1||i>k1||SP[i]==1) return 1; if(s[0]==P&&RP[i]>0) return 1; if(s[i-2]==P&&RP[i]>0) return 1; return 0; } bool right(int i){ if(RS[i]==n-i&&i!=n) return 0; if(i==n||i<k2||SS[i]==1) return 1; if(s[n-1]==P&&RS[i]>0) return 1; if(s[i]==P&&RS[i]>0) return 1; return 0; } void type2(int i){ if(left(i)==1&&right(i)==1) ans[i]=1; } void build2(){ int flag1=0,flag2=0; for(int i=1;i<=n;i++){ if(s[i-1]==R){ if(flag2==1){ k1=i; break; } else flag1=1; } if(s[i-1]==P){ if(flag1==1) flag2=1; } } flag1=flag2=0; for(int i=n;i>=1;i--){ if(s[i-1]==R){ if(flag2==1){ k2=i; break; } else flag1=1; } if(s[i-1]==P){ if(flag1==1) flag2=1; } } return; } void build(){ ers(); for(int i=1;i<=n;i++){ if(s[i-1]==S) SP[i]++; if(s[i-1]==P) PP[i]++; if(s[i-1]==R) RP[i]++; RP[i]+=RP[i-1]; SP[i]+=SP[i-1]; PP[i]+=PP[i-1]; } for(int i=n;i>=1;i--){ if(s[i-1]==S) SS[i]++; if(s[i-1]==P) PS[i]++; if(s[i-1]==R) RS[i]++; RS[i]+=RS[i+1]; SS[i]+=SS[i+1]; PS[i]+=PS[i+1]; } build2(); //cout<<S<<" "<<k1<<" "<<k2<<endl; for(int i=1;i<=n;i++){ if(s[i-1]==S){ if(d==1) type1(i); else type2(i); } } return; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin>>t; while(t--){ cin>>d>>s; n=s.size(); ERS(); S='s',P='p',R='r'; build(); S='p',P='r',R='s'; build(); S='r',P='s',R='p'; build(); for(int i=1;i<=n;i++) cout<<ans[i]; cout<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...