#include "bits/stdc++.h"
using namespace std;
// vector <char> v[1000010];
string solve(string s) {
int n = s.size();
stack <int> p;
stack <int> q;
string ans;
for(int i = 0; i < n; i++) ans += '#';
for(int i = 0; i < n; i++) {
if(s[i] == ')') {
if(p.empty()) {
if(q.empty()) return "impossible";
else {
ans[q.top()] = 'G';
ans[i] = 'B';
q.pop();
}
} else {
ans[p.top()] = 'R';
ans[i] = 'R';
p.pop();
}
} else {
p.push(i);
q.push(i);
}
}
stack <int> thic;
for(int i = 0; i < n; i++) {
if(ans[i] == '#') {
thic.push(i);
} else if (s[i] == ')' && !thic.empty()) {
ans[thic.top()] = 'B';
ans[i] = 'G';
thic.pop();
}
}
if(thic.empty()) return ans;
else return "impossible";
}
const int mod = 1000000000 + 7;
int mem[333][333][333];
int fem[333][333][333];
int dp(int cur, int p, int q) {
if(cur == 0) {
return p == 0;
}
if(mem[cur][p][q] != -1) return mem[cur][p][q];
int ans = 0;
ans += dp(cur - 1, p + 1, q + 1);
if(p > 0) ans += dp(cur - 1, p - 1, q);
else if(q > 0) ans += dp(cur - 1, p, q - 1);
ans %= mod;
return mem[cur][p][q] = ans;
}
int fn(int cur, int p, int q) {
if(cur == 0) {
return q == 0;
}
if(fem[cur][p][q] != -1) return fem[cur][p][q];
int ans = 0;
ans += fn(cur - 1, p + 1, q + 1);
if(p > 1) {
ans += fn(cur - 1, p - 1, max(0, q - 2));
}
ans %= mod;
return fem[cur][p][q] = ans;
}
int main(int argc, char const *argv[])
{
ios_base :: sync_with_stdio (false);
cin.tie(0);
int p;
cin >> p;
int t;
cin >> t;
memset(mem, -1, sizeof mem);
memset(fem, -1, sizeof fem);
while(t--) {
if(p == 1) {
string s;
cin >> s;
cout << solve(s) << '\n';
} else {
int n;
cin >> n;
long long ans = 0;
for(int i = 0; i <= n; i++) {
ans += 1LL * dp(i, 0, 0) * fn(n-i, 0, 0);
ans %= mod;
}
cout << ans << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
278 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
298 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
298 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
298 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
280 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
280 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
280 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
