oj.uz

Submission #61211

# Submission time Handle Problem Language Result Execution time Memory
61211 2018-07-25T11:24:19 Z SpaimaCarpatilor parentrises (BOI18_parentrises) C++17
0 / 100
 4 ms 476 KB 
#include<bits/stdc++.h>

using namespace std;

int N;
char sir[1000009], ans[1000009];
const int mod = 1e9 + 7;

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;
    }
}

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

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);
                int j = 0, k = 0;
                for (int i=1; i<=N; i++)
                {
                    if (ans[i] == 'G')
                    {
                        if (sir[i] == '(') j ++, k ++;
                        else j --, k --;
                        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;
                }
            }
        }
        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);
                int j = 0, k = 0;
                for (int i=N; i>=1; i--)
                {
                    if (ans[i] == 'G')
                    {
                        if (sir[i] == ')') j ++, k ++;
                        else j --, k --;
                        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) printf ("impossible\n");
        else ans[N + 1] = 0, printf ("%s\n", ans + 1);
    }
    return 0;
}
/*dp[0][0][0] = 1;
for (int i=0; i<=N; i++)
    for (int j=0; j<=i; j++)
        for (int k=0; k<=i; k++)
            if (dp[i][j][k] > 0)
            {
                adto (dp[i + 1][j + 1][k + 1], dp[i][j][k]);
                int nj = j, nk = k;
                if (k > j) nk --;
                else nj --;
                if (nj >= 0)
                    adto (dp[i + 1][nj][nk], dp[i][j][k]);
            }
int tests;
scanf ("%d", &tests);
while (tests --)
{
    scanf ("%d", &N);
    int ans = 0;
    for (int i=0; i<=N; i++)
        for (int j=0; j<=N; j++)
            ans += dp[i][j];
}*/
return 0;
}

Compilation message

parentrises.cpp: In function 'int main()':
parentrises.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &type);
 ~~~~~~^~~~~~~~~~~~~
parentrises.cpp:33:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d\n", &tests);
     ~~~~~~^~~~~~~~~~~~~~~~
parentrises.cpp:36: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);
         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 476 KB Output is correct
3 Incorrect 2 ms 476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 476 KB Unexpected end of file - int32 expected

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 476 KB Unexpected end of file - int32 expected

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 476 KB Unexpected end of file - int32 expected