#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
int P;
void solve(){
string s; cin >> s;
int n = s.size();
map<pair<int, int>, bool> dp[n];
string path[n][n + 1][n + 1];
// RBG
if(s[0] == ')' or s[n-1] == '('){
cout << "impossible";
return;
}
dp[0][{0, 1}] = 1, dp[0][{1, 0}] = 1;
dp[0][{1, 1}] = 1;
path[0][0][1] = "R";
path[0][1][1] = "G";
path[0][1][0] = "B";
vector<int> pref(n);
pref[0] = 1;
for(int i = 1;i < n; i++){
pref[i] = pref[i-1] + s[i]==')' ? -1 : 1;
}
for(int i = 1;i < n; i++){
for(auto [pp, y] : dp[i-1]){
int x1 = pp.ff, x2 = pp.ss;
int ok = 0;
int c = s[i]==')' ? -1 : 1;
if(x2 + c >= 0){
ok++;
dp[i][{x1, x2 + c}] = 1;
path[i][x1][x2 + c] = path[i-1][x1][x2] + "R";
}
if(x1 + c >= 0){
ok++;
dp[i][{x1 + c, x2}] = 1;
path[i][x1 + c][x2] = path[i-1][x1][x2] + "B";
}
if(ok == 2){
dp[i][{x1 + c, x2 + c}] = 1;
path[i][x1 + c][x2 + c] = path[i-1][x1][x2] + "G";
}
}
}
if(dp[n-1][{0, 0}]){
cout << path[n-1][0][0];
}else{
cout << "impossible";
}
}
void solve1(){
int n; cin >> n;
map<pair<int, int>, int> dp[n];
dp[0][{0, 1}] = 1, dp[0][{1, 0}] = 1;
dp[0][{1, 1}] = 1;
vector< vector<int> > cnt(n, vector<int>(2, 0));
cnt[0][0] = 1;
for(int i = 1;i < n; i++){
for(auto [pp, y] : dp[i-1]){
int x1 = pp.ff, x2 = pp.ss;
int ok = 0;
int c = -1;
if(x2 + c >= 0){
ok++;
dp[i][{x1, x2 + c}] = (dp[i][{x1, x2 + c}] + y) % mod;
}
if(x1 + c >= 0){
ok++;
dp[i][{x1 + c, x2}] = (dp[i][{x1 + c, x2}] + y) % mod;
}
if(ok){
cnt[i][1] = (cnt[i][1] + cnt[i-1][0] + cnt[i-1][1]) % mod;
}
if(ok == 2){
dp[i][{x1 + c, x2 + c}] = (dp[i][{x1 + c, x2 + c}] + y) % mod;
}
c = 1;
cnt[i][0] = (cnt[i][0] + cnt[i-1][0] + cnt[i-1][1]) % mod;
dp[i][{x1 + c, x2 + c}] = (dp[i][{x1 + c, x2 + c}] + y) % mod;
dp[i][{x1 + c, x2}] = (dp[i][{x1 + c, x2}] + y) % mod;
dp[i][{x1, x2 + c}] = (dp[i][{x1, x2 + c}] + y) % mod;
}
}
cout << cnt[n-1][1] + cnt[n-1][0];
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> P;
int test; cin >> test;
while(test--){
if(P == 1)solve();
else solve1();
cout << '\n';
}
return 0;
}
Compilation message
parentrises.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
96 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16732 KB |
Output is correct |
2 |
Correct |
52 ms |
46772 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
7 ms |
5468 KB |
Output is correct |
5 |
Correct |
43 ms |
42760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16732 KB |
Output is correct |
2 |
Correct |
52 ms |
46772 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
7 ms |
5468 KB |
Output is correct |
5 |
Correct |
43 ms |
42760 KB |
Output is correct |
6 |
Runtime error |
131 ms |
262144 KB |
Execution killed with signal 9 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16732 KB |
Output is correct |
2 |
Correct |
52 ms |
46772 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
7 ms |
5468 KB |
Output is correct |
5 |
Correct |
43 ms |
42760 KB |
Output is correct |
6 |
Runtime error |
131 ms |
262144 KB |
Execution killed with signal 9 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |