This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |