oj.uz

Submission #64309

# Submission time Handle Problem Language Result Execution time Memory
64309 2018-08-04T04:00:10 Z antimirage parentrises (BOI18_parentrises) C++17
100 / 100
 273 ms 110116 KB 
#include <iostream>
#include <assert.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <random>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 305, mod = 1e9 + 7, M = 1e6 + 5;

int type, tests, dp[N][N + N][N], x, res;

int pref[2][M], n, mn[2], bal1, bal2, sum[2][M], bal;

char s[M], ans[M];

bool fl;

main()
{
    cin >> type >> tests;

    if (type == 2)
    {
        dp[0][0][0] = 1;

        for (int i = 1; i <= 300; i++)
            for (int j = 0; j <= i + i; j++)
                for (int k = 0; k <= i; k++)
                {
                    if (j >= 2 && k >= 1)
                    {
                        dp[i][j][k] += dp[i - 1][j - 2][k - 1];
                        dp[i][j][k] %= mod;
                    }
                    if (j < i + i)
                    {
                        if (k == 0)
                        {
                            dp[i][j][k] += dp[i - 1][j + 1][k];
                            dp[i][j][k] %= mod;
                            dp[i][j][k] += dp[i - 1][j + 1][k + 1];
                            dp[i][j][k] %= mod;
                            dp[i][j][k] += dp[i - 1][j + 1][k + 2];
                            dp[i][j][k] %= mod;
                        }
                        else
                        {
                            dp[i][j][k] += dp[i - 1][j + 1][k + 2];
                            dp[i][j][k] %= mod;
                        }
                    }
                }
        while (tests--)
        {
            res = 0;
            scanf("%d", &x);
            for (int i = 0; i <= x; i++)
                res += dp[x][i][0], res %= mod;

            printf("%d\n", res);
        }
    }
    else
    {
        while (tests--)
        {
            fl = false;
            bal = 0;
            scanf("%s", s + 1);

            n = strlen(s + 1);

            if (s[n] == '(')
                    fl = 1;

            for (int i = 1; i <= n; i++)
            {
                pref[0][i] = pref[1][i] = 0;
                sum[0][i] = sum[1][i] = 0;
                if ( s[i] == '(' )
                    pref[0][i] = 1, pref[1][i] = 1, ans[i] = 'G', bal += 2;
                else
                {
                    if (pref[0][i - 1] > pref[1][i - 1])
                        ans[i] = 'R', pref[0][i] = -1;
                    else
                        ans[i] = 'B', pref[1][i] = -1;

                    bal--;
                }
                pref[0][i] += pref[0][i - 1];
                pref[1][i] += pref[1][i - 1];

                if (bal < 0)
                    fl = 1;
            }
            bal1 = pref[0][n];
            bal2 = pref[1][n];
            mn[0] = mn[1] = 1e9 + 7;

            for (int i = n; i >= 1; i--)
            {
                mn[0] = min( mn[0], pref[0][i] );
                mn[1] = min( mn[1], pref[1][i] );
                if ( ans[i] == 'R' && mn[1] > 0 )
                {
                    sum[1][i] = -1;
                    ans[i] = 'G';
                    mn[1]--;
                    bal2--;
                }
                if ( ans[i] == 'B' && mn[0] > 0)
                {
                    sum[0][i] = -1;
                    ans[i] = 'G';
                    mn[0]--;
                    bal1--;
                }
            }
            for (int i = 1; i <= n; i++)
            {
                sum[0][i] += sum[0][i - 1];
                sum[1][i] += sum[1][i - 1];
                pref[0][i] += sum[0][i];
                pref[1][i] += sum[1][i];
            }
            mn[0] = mn[1] = 1e9 + 7;

            for (int i = n; i >= 1; i--)
            {
                mn[0] = min( mn[0], pref[0][i] );
                mn[1] = min( mn[1], pref[1][i] );
                if (s[i] == ')') continue;
                if (mn[0] > 0 && bal1 > bal2)
                {
                    ans[i] = 'B';
                    mn[0]--;
                    bal1--;
                }
                else if (mn[1] > 0)
                {
                    ans[i] = 'R';
                    mn[1]--;
                    bal2--;
                }
            }
            if (bal < 0 || bal > n) fl = 1;

            reverse(s + 1, s + n + 1);

            bal = 0;

            for (int i = 1; i <= n; i++)
            {
                if ( s[i] == '(' )
                    bal--;
                else
                    bal += 2;

                if (bal < 0)
                    fl = 1;
            }
            if (bal < 0 || bal > n) fl = 1;

            if (fl)
                puts("impossible");
            else
            {
                for (int i = 1; i <= n; i++)
                    printf("%c", ans[i]);
                printf("\n");
            }
        }
    }
}

Compilation message

parentrises.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
parentrises.cpp: In function 'int main()':
parentrises.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
parentrises.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%s", s + 1);
             ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 556 KB Output is correct
2 Correct 3 ms 564 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 740 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 556 KB Output is correct
2 Correct 3 ms 564 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 740 KB Output is correct
6 Correct 3 ms 740 KB Output is correct
7 Correct 4 ms 740 KB Output is correct
8 Correct 4 ms 740 KB Output is correct
9 Correct 3 ms 740 KB Output is correct
10 Correct 3 ms 740 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 4 ms 780 KB Output is correct
15 Correct 4 ms 796 KB Output is correct
16 Correct 9 ms 796 KB Output is correct
17 Correct 14 ms 2460 KB Output is correct
18 Correct 9 ms 2460 KB Output is correct
19 Correct 13 ms 2460 KB Output is correct
20 Correct 13 ms 2460 KB Output is correct
21 Correct 65 ms 2460 KB Output is correct
22 Correct 115 ms 19356 KB Output is correct
23 Correct 73 ms 19356 KB Output is correct
24 Correct 102 ms 19356 KB Output is correct
25 Correct 138 ms 19356 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 109960 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 109960 KB Output is correct
2 Correct 224 ms 110116 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 109960 KB Output is correct
2 Correct 224 ms 110116 KB Output is correct
3 Correct 233 ms 110116 KB Output is correct