#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;
}
}
namespace generator {
const int N = 13;
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);
int j = 0, k = 0;
for (int i=1; i<=N; i++)
{
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;
assert (j <= k);
}
if (!ok) assert (j + k == 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 --;
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;
assert (j <= k);
}
if (!ok) assert (j + k == 0);
}
}
if (!ok) printf ("impossible\n");
else
{
for (int i=1; i<=N; i++)
printf ("%c", ans[i]);
printf ("\n");
}
}
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 'void generator::genTests()':
parentrises.cpp:58: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:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &type);
~~~~~~^~~~~~~~~~~~~
parentrises.cpp:77:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d\n", &tests);
~~~~~~^~~~~~~~~~~~~~~~
parentrises.cpp:80: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);
~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
472 KB |
Output is correct |
| 3 |
Correct |
3 ms |
524 KB |
Output is correct |
| 4 |
Correct |
4 ms |
524 KB |
Output is correct |
| 5 |
Correct |
3 ms |
524 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
524 KB |
Output is correct |
| 2 |
Correct |
3 ms |
524 KB |
Output is correct |
| 3 |
Correct |
3 ms |
524 KB |
Output is correct |
| 4 |
Correct |
2 ms |
524 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
524 KB |
Output is correct |
| 2 |
Correct |
3 ms |
524 KB |
Output is correct |
| 3 |
Correct |
3 ms |
524 KB |
Output is correct |
| 4 |
Correct |
2 ms |
524 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| 6 |
Correct |
2 ms |
552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
552 KB |
Output is correct |
| 8 |
Correct |
3 ms |
552 KB |
Output is correct |
| 9 |
Correct |
3 ms |
552 KB |
Output is correct |
| 10 |
Correct |
3 ms |
552 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
524 KB |
Output is correct |
| 2 |
Correct |
3 ms |
524 KB |
Output is correct |
| 3 |
Correct |
3 ms |
524 KB |
Output is correct |
| 4 |
Correct |
2 ms |
524 KB |
Output is correct |
| 5 |
Correct |
3 ms |
552 KB |
Output is correct |
| 6 |
Correct |
2 ms |
552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
552 KB |
Output is correct |
| 8 |
Correct |
3 ms |
552 KB |
Output is correct |
| 9 |
Correct |
3 ms |
552 KB |
Output is correct |
| 10 |
Correct |
3 ms |
552 KB |
Output is correct |
| 11 |
Correct |
4 ms |
552 KB |
Output is correct |
| 12 |
Correct |
4 ms |
552 KB |
Output is correct |
| 13 |
Correct |
4 ms |
572 KB |
Output is correct |
| 14 |
Correct |
4 ms |
572 KB |
Output is correct |
| 15 |
Correct |
4 ms |
584 KB |
Output is correct |
| 16 |
Correct |
8 ms |
584 KB |
Output is correct |
| 17 |
Correct |
13 ms |
856 KB |
Output is correct |
| 18 |
Correct |
11 ms |
856 KB |
Output is correct |
| 19 |
Correct |
12 ms |
856 KB |
Output is correct |
| 20 |
Correct |
12 ms |
856 KB |
Output is correct |
| 21 |
Correct |
53 ms |
1368 KB |
Output is correct |
| 22 |
Correct |
96 ms |
3528 KB |
Output is correct |
| 23 |
Correct |
56 ms |
3528 KB |
Output is correct |
| 24 |
Correct |
101 ms |
3528 KB |
Output is correct |
| 25 |
Correct |
112 ms |
3528 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3528 KB |
Unexpected end of file - int32 expected |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3528 KB |
Unexpected end of file - int32 expected |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3528 KB |
Unexpected end of file - int32 expected |
