Submission #61241

#	Time	Username	Problem	Language	Result	Execution time	Memory
61241		SpaimaCarpatilor	parentrises (BOI18_parentrises)	C++17	100 / 100	96 ms	3528 KiB

parentrises

#include<bits/stdc++.h>

using namespace std;

int N;
char sir[1000009], ans[1000009];
const int mod = 1e9 + 7;
const int maxN = 300;
int cnt[maxN + 5], dp[maxN + 5][maxN + 5][2][4];

void adto (int &x, int y) {x += y; if (x >= mod) x -= mod;}

void addGreens (int l, int r)
{
    while (1)
    {
        while (sir[l] == ')' && l <= N) l ++;
        while (sir[r] == '(' && r >= 1) r --;
        if (l == N + 1 || r == 0) break;
        if (l < r) ans[l] = ans[r] = 'G', l ++, r --;
        else break;
    }
}

void fillOutRB (bool &ok)
{
    int j = 0, k = 0;
    for (int i=1; i<=N; i++)
    {
        assert (j <= k);
        if (ans[i] == 'G')
        {
            if (sir[i] == '(') j ++, k ++;
            else j --, k --;
            if (j < 0 || k < 0) ok = 0;
            continue;
        }
        if (sir[i] == '(')
        {
            if (j >= k) k ++, ans[i] = 'B';
            else j ++, ans[i] = 'R';
            continue;
        }
        if (j < k) k --, ans[i] = 'B';
        else j --, ans[i] = 'R';
        if (j < 0) ok = 0;
    }
    if (!ok) assert (j + k == 0);
}

namespace generator {
    const int N = 3;
    bool canDo = 0;
    void back (int pos, int i, int j)
    {
        if (canDo) return ;
        if (i < 0 || j < 0) return ;
        if (pos == N + 1)
        {
            if (i + j == 0)
                canDo = 1;
            return ;
        }
        back (pos + 1, i + sir[pos], j + sir[pos]);
        back (pos + 1, i + sir[pos], j);
        back (pos + 1, i, j + sir[pos]);
    }

    void genTests ()
    {
        vector < string > input;
        for (int msk = 0; msk < (1 << N); msk ++)
        {
            for (int i=0; i<N; i++)
                sir[i + 1] = (((msk & (1 << i)) > 0) ? +1 : -1);
            canDo = 0, back (1, 0, 0);
            if (canDo)
            {
                string curr;
                for (int i=1; i<=N; i++)
                    if (sir[i] == +1) curr.push_back ('(');
                    else curr.push_back (')');
                input.push_back (curr);
            }
        }
        printf ("%d\n", input.size ());
        for (auto s : input)
            printf ("%s\n", s.c_str ());
        exit (0);
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

//generator::genTests ();

int type;
scanf ("%d", &type);
if (type == 1)
{
    int tests;
    scanf ("%d\n", &tests);
    while (tests --)
    {
        scanf ("%s\n", sir + 1), N = strlen (sir + 1);
        int balance = 0;
        for (int i=1; i<=N; i++)
            if (sir[i] == '(') balance ++;
            else balance --;
        for (int i=1; i<=N + 1; i++)
            ans[i] = 0;
        bool ok = 1;
        if (balance > 0)
        {
            ///I'll use first X + balance open brackets and last X closed ones where X is maximal so that all the closed brackets come after the open ones
            int l = 1, r = N;
            while (balance > 0)
            {
                while (sir[r] == '(' && r >= 1) r --;
                if (r == 0)
                {
                    ok = 0;
                    break;
                }
                ans[r] = 'G', r --;
                balance --;
            }
            if (ok)
                addGreens (l, r);
        }
        else
        {
            balance = -balance;
            ///same as above
            int l = 1, r = N;
            while (balance > 0)
            {
                while (sir[l] == ')' && l <= N) l ++;
                if (l == N + 1)
                {
                    ok = 0;
                    break;
                }
                ans[l] = 'G', l ++;
                balance --;
            }
            if (ok)
                addGreens (l, r);
        }
        if (ok)
            fillOutRB (ok);
        if (!ok) printf ("impossible\n");
        else
        {
            for (int i=1; i<=N; i++)
                printf ("%c", ans[i]);
            printf ("\n");
        }
    }
    return 0;
}
///a state is defined by:
///j, kj (which means (j, k) = (j, j + kj))
///the current phase: 0/1/2/3
///in phase 0 we need to take any ( and put it as green

///in phases 1 and 2 we can't put any green and we can't have the subsequence () -
///phase 1 is as long as we have )
///phase 2 is as long as we have ( after phase 1 (and after that both phases must stop since we can't have () )

///in phase 3 we need to take any ) and put it as green
///complexity: N^2
///dp[i][j][kj][phase]
dp[0][0][0][0] = 1;
for (int i=0; i<maxN; i++)
{
    for (int j=0; j<=i; j++)
        for (int kj=0; kj<2; kj++)
            for (int phase=0; phase<4; phase++)
                if (dp[i][j][kj][phase] > 0)
                    for (int br = 0; br < 2; br ++)
                        for (int nPhase = phase; nPhase < 4; nPhase ++)
                        {
                            int ni = i + 1, nj = j, nk = j + kj;
                            if (phase == 1 && br == 0 && nPhase == 1) continue;
                            if (phase == 2 && br == 1 && nPhase == 2) continue;
                            if (phase == 1 && nPhase == 2 && br != 0) continue;
                            if (phase == 0 && br == 0 && nPhase == 1) continue;
                            if (phase == 0 && 1 <= nPhase && nPhase <= 2 && br == 1) continue;
                            if (nPhase == 3 && 0 <= phase && phase <= 2 && br == 0) continue;
                            if ((nPhase == 3 && br == 1) || (nPhase == 0 && br == 0))
                            {
                                if (br == 0) nj ++, nk ++;
                                else nj --, nk --;
                            }
                            else
                            {
                                if (br == 0)
                                {
                                    if (nj >= nk) nk ++;
                                    else nj ++;
                                }
                                else
                                {
                                    if (nj < nk) nk --;
                                    else nj --;
                                }
                            }
                            if (nj >= 0 && nk >= 0)
                                adto (dp[ni][nj][nk - nj][nPhase], dp[i][j][kj][phase]);
                        }
    for (int phase = 0; phase < 4; phase ++)
        adto (cnt[i + 1], dp[i + 1][0][0][phase]);
}
int tests;
scanf ("%d", &tests);
while (tests --)
{
    scanf ("%d", &N);
    printf ("%d\n", cnt[N]);
}
return 0;
}

Compilation message (stderr)

parentrises.cpp: In function 'void generator::genTests()':
parentrises.cpp:86:38: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::__cxx11::basic_string<char> >::size_type {aka long unsigned int}' [-Wformat=]
         printf ("%d\n", input.size ());
                         ~~~~~~~~~~~~~^
parentrises.cpp: In function 'int main()':
parentrises.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &type);
 ~~~~~~^~~~~~~~~~~~~
parentrises.cpp:105:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d\n", &tests);
     ~~~~~~^~~~~~~~~~~~~~~~
parentrises.cpp:108:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%s\n", sir + 1), N = strlen (sir + 1);
         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
parentrises.cpp:219:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &tests);
 ~~~~~~^~~~~~~~~~~~~~
parentrises.cpp:222:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~

• 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