Submission #73604

#	Time	Username	Problem	Language	Result	Execution time	Memory
73604		yusufake	parentrises (BOI18_parentrises)	C++98	100 / 100	64 ms	5544 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;

#define _ int v, int tl, int tr, int l, int r
#define tm (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r

#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pp pair<int,int>

const int mod = 1e9 + 7;
const int N = 1e6 + 6;

int V[N],v,zz,ww,n,i,p,ok;
char s[N],ans[N];

int MM[301][301];
int g(int n, int k){
    if(k < 0) return 0;
    if(n == 0) return !k;
    int &r = MM[n][k];
    if(r != -1) return r;
    return r = (g(n-1,k+1) + g(n-1,k-1)) % mod;
}
int M[301][301];
int f(int i, int k){
    int t = i-k;
    if(t&1) return 0;
    t >>= 1;
    if(t+k > t+t) return 0;
    if(!i) return !k;
    if(k<0) return 0;
    int &r = M[i][k];
    if(r != -1) return r;
    r = 0;
    for(int j=i-1; j>=0 ; j--)
        r = (r + 1LL * f(j,k-1) * g(i-j-1,0)) % mod;
    return r;
}

int T[301],asd,j;
int main(){
    scanf("%d%d",&zz,&ww);
    if(zz == 2){
        memset(M,-1,sizeof M);
        memset(MM,-1,sizeof MM);
        for(i=0;i<301;i++)
            for(j=0;j<=i;j++)
                T[i] = (T[i] + f(i,j)) % mod;
        for(;ww--;){
            scanf("%d",&n);
            asd = 0;
            for(i=0;i<=n;i++)
                for(j=n-i; j>=0 ;j--)
                    asd = (asd + 1LL*T[i]*T[j]%mod*g(n-i-j,0)) % mod;
            printf("%d\n", asd);
        }
        return 0;
    }

    for(;ww--;){
        scanf(" %s",s+1);
        n = strlen(s+1);
        p = v = 0;
        ok = 1;
        for(i=1;i<=n;i++) ans[i] = 'G';
        ans[n+1] = 0;
        for(i=1;i<=n;i++){
            p += s[i] == ')' ? 1 : -1;
            if(s[i] == ')') V[++v] = i;
            if(p > 0){
                ans[ V[v--] ] = 'B';
                ans[ V[v--] ] = 'R';
                p = 0;
                if(v == -1) { ok=0; break; }
            }
        }
        p = v = 0;
        for(i=n; i ;i--){
            p += s[i] == '(' ? 1 : -1;
            if(s[i] == '(') V[++v] = i;
            if(p > 0){
                ans[ V[v--] ] = 'B';
                ans[ V[v--] ] = 'R';
                p = 0;
                if(v == -1) { ok=0; break; }
            }
        }
        puts(ok ? ans+1 : "impossible");
    }

    return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'int main()':
parentrises.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&zz,&ww);
     ~~~~~^~~~~~~~~~~~~~~~
parentrises.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&n);
             ~~~~~^~~~~~~~~
parentrises.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s",s+1);
         ~~~~~^~~~~~~~~~~

• 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