oj.uz

Submission #255239

# Submission time Handle Problem Language Result Execution time Memory
255239 2020-07-31T15:54:26 Z Kastanda parentrises (BOI18_parentrises) C++11
100 / 100
 85 ms 55736 KB 
// M
#include<bits/stdc++.h>
using namespace std;
const int MXN = 1000006, N = 303, Mod = 1e9 + 7;
int Sub;
void SolveSub1()
{
        int q;
        char S[MXN];
        fill(S, S + MXN, 0);
        scanf("%d", &q);
        for (; q; q --)
        {
                scanf("%s", S);
                int n = strlen(S);
                vector < int > C(n, 0), Stk, OP;
                for (int i = 0; i < n; i ++)
                {
                        if (S[i] == '(')
                                Stk.push_back(i);
                        else if (Stk.size())
                                C[Stk.back()] = C[i] = 1, Stk.pop_back();
                        else
                                OP.push_back(i);
                }
                bool Fail = 0;
                vector < int > Kts, PO;
                for (int i = n - 1; ~ i; i --)
                {
                        if (Stk.size())
                        {
                                if (Stk.back() == i)
                                {
                                        if (!Kts.size())
                                                {Fail = 1; break;}
                                        C[Kts.back()] += 2;
                                        Kts.pop_back();
                                        C[Stk.back()] += 2;
                                        Stk.pop_back();
                                        continue;
                                }
                                if (S[i] == '(')
                                        continue;
                                Kts.push_back(i);
                        }
                        else
                        {
                                if (OP.size() && OP.back() == i)
                                {
                                        PO.push_back(OP.back());
                                        OP.pop_back();
                                        continue;
                                }
                                if (S[i] == ')')
                                        continue;
                                if (PO.size())
                                {
                                        C[PO.back()] += 2;
                                        PO.pop_back();
                                        C[i] += 2;
                                }
                        }
                }
                if (PO.size() || OP.size() || Stk.size())
                        Fail = 1;
                fill(S, S + n, 0);
                if (Fail)
                        printf("impossible\n");
                else
                {
                        for (int i = 0; i < n; i ++)
                                printf("%c", "RBG"[C[i] - 1]);
                        printf("\n");
                }
        }
        exit(0);
}
int dp[N][N][N], dp2[N][N], R[N], F[N];
inline void Add(int &a, int b)
{
        a += b;
        if (a >= Mod)
                a -= Mod;
}
inline void SolveSub2()
{
        int n = 300;
        F[0] = 1;
        dp2[0][0] = 1;
        dp[0][0][0] = 1;
        for (int i = 0; i < n; i ++)
        {
                for (int j = 0; j <= i; j ++)
                {
                        // '('
                        Add(dp2[i + 1][j + 1], dp2[i][j]);
                        // ')'
                        if (j) Add(dp2[i + 1][j - 1], dp2[i][j]);
                        for (int h = 0; h <= i; h ++)
                        {
                                // '('
                                Add(dp[i + 1][j + 1][h + 1], dp[i][j][h]);
                                // ')'
                                if (j)
                                        Add(dp[i + 1][j - 1][h], dp[i][j][h]);
                                else if (h)
                                {
                                        Add(dp[i + 1][j][h - 1], dp[i][j][h]);
                                        if (j == 0)
                                                Add(F[i + 1], dp[i][j][h]);
                                }
                        }
                }
        }
        for (int i = 1; i <= n; i ++)
                for (int j = 0; j <= i; j ++)
                        for (int h = 0; j + h <= i; h ++)
                                R[i] = (R[i] + 1LL * F[j] * F[h] % Mod * dp2[i - j - h][0]) % Mod;

        int q;
        scanf("%d", &q);
        for (; q; q --)
        {
                scanf("%d", &n);
                printf("%d\n", R[n]);
        }
        return ;
}
int main()
{
        scanf("%d", &Sub);
        if (Sub == 1)
                SolveSub1();
        else
                SolveSub2();
        return 0;
}

Compilation message

parentrises.cpp: In function 'void SolveSub1()':
parentrises.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &q);
         ~~~~~^~~~~~~~~~
parentrises.cpp:14:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%s", S);
                 ~~~~~^~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &Sub);
         ~~~~~^~~~~~~~~~~~
parentrises.cpp: In function 'void SolveSub2()':
parentrises.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &q);
         ~~~~~^~~~~~~~~~
parentrises.cpp:124:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &n);
                 ~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 1 ms 1280 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 2 ms 1280 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1280 KB Output is correct
2 Correct 1 ms 1280 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1280 KB Output is correct
2 Correct 1 ms 1280 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Correct 1 ms 1280 KB Output is correct
8 Correct 1 ms 1280 KB Output is correct
9 Correct 1 ms 1280 KB Output is correct
10 Correct 2 ms 1280 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1280 KB Output is correct
2 Correct 1 ms 1280 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Correct 1 ms 1280 KB Output is correct
8 Correct 1 ms 1280 KB Output is correct
9 Correct 1 ms 1280 KB Output is correct
10 Correct 2 ms 1280 KB Output is correct
11 Correct 2 ms 1408 KB Output is correct
12 Correct 2 ms 1408 KB Output is correct
13 Correct 2 ms 1280 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct
15 Correct 3 ms 1408 KB Output is correct
16 Correct 8 ms 1536 KB Output is correct
17 Correct 9 ms 1920 KB Output is correct
18 Correct 7 ms 1536 KB Output is correct
19 Correct 7 ms 1792 KB Output is correct
20 Correct 10 ms 2048 KB Output is correct
21 Correct 68 ms 2552 KB Output is correct
22 Correct 75 ms 7156 KB Output is correct
23 Correct 54 ms 3324 KB Output is correct
24 Correct 61 ms 5232 KB Output is correct
25 Correct 68 ms 6904 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 55672 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 55672 KB Output is correct
2 Correct 85 ms 55672 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 55672 KB Output is correct
2 Correct 85 ms 55672 KB Output is correct
3 Correct 85 ms 55736 KB Output is correct