#include <iostream>
#include <assert.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <string.h>
#include <random>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#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 = 1e6 + 5;
int type, tests, pref[2][N], n, mn[2], bal1, bal2, sum[2][N], bal;
char s[N], ans[N];
bool fl;
main()
{
cin >> type >> tests;
while (tests--)
{
if (type == 1)
{
fl = false;
scanf("%s", s + 1);
n = strlen(s + 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];
}
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;
if (fl)
puts("impossible");
else
{
for (int i = 1; i <= n; i++)
printf("%c", ans[i]);
printf("\n");
}
}
else{}
}
}
Compilation message
parentrises.cpp:31:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
parentrises.cpp: In function 'int main()':
parentrises.cpp:40: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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
564 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
564 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
564 KB |
Unexpected end of file - int32 expected |
