Submission #1087392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087392		m5588ohammed	RPS string (innopolis2021_final_C)	C++14	37 / 100	65 ms	37092 KiB

Main

#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],L[500002],R[500002];
int PS[500002],RS[500002],SS[500002];
string s;   
int n,d;
void ers(){
    for(int i=1;i<=n+1;i++) PP[i]=RP[i]=SP[i]=PS[i]=RS[i]=SS[i]=L[i]=R[i]=0;
    return; 
}
void ERS(){
    for(int i=1;i<=n+1;i++) PP[i]=RP[i]=SP[i]=L[i]=R[i]=ans[i]=0;
    return; 
}
void type1(int k){
    if(RP[k]>0&&PP[k]>0){
        if(RS[k]>0&&PS[k]>0) ans[k]=1;
        if(RS[k]==0) ans[k]=1;
    }
    if(RP[k]==0){
        if(RS[k]>0&&PS[k]>0) ans[k]=1;
        if(RS[k]==0) ans[k]=1;
    }
    return;
}
void type2(int k){

}
void build1(){
    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];
    }
    for(int i=1;i<=n;i++){
        if(s[i-1]=='s'){
            if(d==1) type1(i);
            else type2(i);
        }
    }
    return;
}
void build2(){
    ers();
    for(int i=1;i<=n;i++){
        if(s[i-1]=='p') SP[i]++;
        if(s[i-1]=='r') PP[i]++;
        if(s[i-1]=='s') 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]=='p') SS[i]++;
        if(s[i-1]=='r') PS[i]++;
        if(s[i-1]=='s') RS[i]++;
        RS[i]+=RS[i+1];
        SS[i]+=SS[i+1];
        PS[i]+=PS[i+1];
    }
    for(int i=1;i<=n;i++){
        if(s[i-1]=='p'){
            if(d==1) type1(i);
            else type2(i);
        }
    }
    return;
}
void build3(){
    ers();
    for(int i=1;i<=n;i++){
        if(s[i-1]=='r') SP[i]++;
        if(s[i-1]=='s') PP[i]++;
        if(s[i-1]=='p') 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]=='r') SS[i]++;
        if(s[i-1]=='s') PS[i]++;
        if(s[i-1]=='p') RS[i]++;
        RS[i]+=RS[i+1];
        SS[i]+=SS[i+1];
        PS[i]+=PS[i+1];
    }
    for(int i=1;i<=n;i++){
        if(s[i-1]=='r'){
            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();
        build1();
        build2();
        build3();
        for(int i=1;i<=n;i++) cout<<ans[i];
        cout<<endl;
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 0 / 7
• Subtask 6: 0 / 13
• Subtask 7: 0 / 10
• Subtask 8: 0 / 33