#include "bits/stdc++.h"
using namespace std;
#define int long long
pair <int,int> mn(pair <int,int> a, pair <int,int> b) {
if(max(a.first, a.second) < max(b.first, b.second) ) return a;
return b;
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
int q;
cin >> q;
while(q --) {
string str;
cin >> str;
int n = (int)str.size();
// pair <int,int> dp[n][3];
// for(int i = 0; i < n; i ++) {
// for(int j = 0; j < 3; j ++) dp[i][j] = {1e9,1e9};
// }
// for(int i = 0; i < n; i ++) { // 0 - red, 1 - blue, 2 - green
// if(!i) {
// if(str[i] == ')') {
// cout << "impossible\n";
// goto end;
// }else {
// dp[i][0] = {1, 0};
// dp[i][1] = {0, 1};
// dp[i][2] = {1, 1};
// }
// }else {
// if(str[i] == ')') {
// for(int j = 0; j < 3; j ++) {
// if(min(dp[i-1][j].first, dp[i-1][j].second) > 0) {
// dp[i][2] = mn(dp[i][j], make_pair(dp[i-1][j].first-1, dp[i-1][j].second-1));
// }
// if(dp[i-1][j].first > 0) {
// dp[i][0] = mn(dp[i][j], make_pair(dp[i-1][j].first - 1, dp[i-1][j].second));
// }
// if(dp[i-1][j].second > 0) {
// dp[i][1] = mn(dp[i][j], make_pair(dp[i-1][j].first, dp[i-1][j].second - 1));
// }
// }
// if(dp[i][0].first == 1e9 && dp[i][1].first == 1e9 && dp[i][2].first == 1e9) {
// cout << "impossible\n";
// goto end;
// }
// }else {
// for(int j = 0; j < 3; j ++) {
// dp[i][2] = mn(dp[i][2], {dp[i-1][j].first + 1, dp[i-1][j].second + 1});
// dp[i][0] = mn(dp[i][0], {dp[i-1][j].first + 1, dp[i-1][j].second});
// dp[i][1] = mn(dp[i][1], {dp[i-1][j].first, dp[i-1][j].second + 1});
// }
// }
// }
// }
// if(dp[n-1][0].first == 0 && dp[n-1][2].second == 0) cout << "possible\n";
// else if(dp[n-1][0].first == 0 && dp[n-1][2].second == 0) cout << "possible\n";
// else if(dp[n-1][0].first == 0 && dp[n-1][2].second == 0) cout << "possible\n";
// else cout << "impossible\n";
// end:;
// continue;
vector <pair <int,int>> sequence;
int cnt = 1;
for(int i = 1; i < n; i ++) {
if(str[i] == str[i - 1]) {
cnt ++;
}else {
sequence.push_back({cnt, (str[i-1] == '(')});
cnt = 1;
}
}
if(cnt) {
sequence.push_back({cnt, (str[n-1] == '(')});
}
if(sequence.size() % 2 == 1) {
cout << "impossible\n";
continue;
}
if(sequence[0].second == -1) {
cout << "impossible\n";
continue;
}
string ans;
for(int i = 0; i < sequence.size()-1; i += 2) {
int v = sequence[i].first, u = sequence[i+1].first;
if(v == u) {
v += u;
while(v --) ans += 'G';
}
else if(v * 2 == u) {
while(v --) ans += 'G';
int U = u;
u/=2;
while(u --) ans += 'R';
u = U;
u /= 2;
while(u --) ans += 'B';
}else if(u * 2 == v) {
int V = v;
v/=2;
while(v --) ans += 'R';
v = V;
v /= 2;
while(v --) ans += 'B';
while(u --) ans += 'G';
}else {
cout << "impossible\n";
goto end;
}
}
cout << ans << "\n";
end:;
continue;
}
return 0;
}
Compilation message
parentrises.cpp: In function 'int main()':
parentrises.cpp:91:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i = 0; i < sequence.size()-1; i += 2) {
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected integer, but "impossible" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected integer, but "impossible" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected integer, but "impossible" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
