#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;
int type, tests, dp[N][N + N][N], x, res;
int pref[2][N], n, mn[2], bal1, bal2, sum[2][N], bal;
char s[N], ans[N];
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);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
536 KB |
Output is correct |
| 3 |
Correct |
3 ms |
536 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
536 KB |
Output is correct |
| 3 |
Correct |
3 ms |
536 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
2 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
536 KB |
Output is correct |
| 3 |
Correct |
3 ms |
536 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
2 ms |
596 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
238 ms |
109972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
238 ms |
109972 KB |
Output is correct |
| 2 |
Correct |
235 ms |
109972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
238 ms |
109972 KB |
Output is correct |
| 2 |
Correct |
235 ms |
109972 KB |
Output is correct |
| 3 |
Correct |
209 ms |
109972 KB |
Output is correct |
