Submission #69998

#	Time	Username	Problem	Language	Result	Execution time	Memory
69998		vanogam	parentrises (BOI18_parentrises)	C++14	100 / 100	399 ms	216968 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;
long long a,s,d[303][303][303],d1[1000002],pas[303],pas1[302],f,g,h,j,k,l,i,n,m,mod=1000000007;
stack<int> q1,q2;
main(){
    ios::sync_with_stdio(0);
    cin>>j;
    if(j==1){
        cin>>n;
        string x;


        for(i=0;i<n;i++){
            cin>>x;
            j=-1;f=0;
            while(q1.size()) q1.pop();
            while(q2.size()) q2.pop();
            for(a=0;a<x.size();a++){
                d1[a]=0;
                if(x[a]=='(') f++;
                else {
                    if(f) {q1.push(a);f--;}
                    else {
                        if(q1.empty()) {cout<<"impossible\n";break;}
                        d1[a]=1;
                        d1[q1.top()]=2;
                        q1.pop();
                        j=a;//cout<<"*";
                    }
                }
            }
            f=0;
            if(a!=x.size()) continue;
            for(a=x.size()-1;a>j;a--){//cout<<"*";
                if(x[a]==')') f++;
                else {
                    if(f) {q2.push(a);f--;}
                    else {
                        if(q2.empty()) {cout<<"impossible\n";break;}
                        d1[a]=1;
                        d1[q2.top()]=2;
                        q2.pop();
                        //j=a;
                    }
                }
            }
            if(a!=j) continue;
            for(a=0;a<x.size();a++){
                if(d1[a]==0) cout<<"G";
                if(d1[a]==1) cout<<"R";
                if(d1[a]==2) cout<<"B";
            }
            cout<<endl;
        }
    }
    else{
        cin>>n;
        d[0][0][0]=1;
        for(i=0;i<=300;i++){
            for(a=0;a<=300;a++){
                for(j=0;j<=300;j++){
                    d[i+1][a+1][j]+=d[i][a][j];
                    if(d[i+1][a+1][j]>=mod) d[i+1][a+1][j]-=mod;
                    if(a){
                        d[i+1][a-1][j+1]+=d[i][a][j];
                        if(d[i+1][a-1][j+1]>=mod) d[i+1][a-1][j+1]-=mod;
                    }
                    else{
                        pas[i]+=d[i][0][j];
                        if(pas[i]>mod) pas[i]-=mod;
                        if(j){

                            d[i+1][0][j-1]+=d[i][0][j];
                            if(d[i+1][0][j-1]>=mod) d[i+1][0][j-1]-=mod;
                            pas1[i+1]+=d[i+1][0][j-1];
                            if(pas1[i+1]>mod) pas1[i+1]-=mod;
                        }
                    }
                }
            }
        }
    pas1[0]=1;
        for(i=0;i<n;i++){
            cin>>a;
            k=0;
            for(j=0;j<=a;j++){//cout<<pas[j]<<" "<<pas1[j]<<endl;
                k=(k+pas1[j]*pas[a-j])%mod;
            }
            cout<<k<<endl;
        }
    }
}

Compilation message (stderr)

parentrises.cpp:5:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
parentrises.cpp: In function 'int main()':
parentrises.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(a=0;a<x.size();a++){
                     ~^~~~~~~~~
parentrises.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(a!=x.size()) continue;
                ~^~~~~~~~~~
parentrises.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(a=0;a<x.size();a++){
                     ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28