| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 96611 | josiftepe | parentrises (BOI18_parentrises) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int dp[305][305][305];
const int MOD = 1e9 + 7;
int rek(int at, int open, int closed){
if(at == 0){
if(closed == 0){
return 1;
}
return 0;
}
if(dp[at][open][closed] != -1){
return dp[at][open][closed];
}
int ret = 0;
ret += rek(at - 1, open + 2, closed + 1);
if(open > 0){
ret += rek(at - 1, open - 1, max(closed - 2, 0));
}
return dp[at][open][closed] = ret % MOD;
}
void solve(string s){
string ret = s;
for(int i = 0; i < s.size(); i ++){
ret[i] = '?';
}
stack<int> st1, st2;
for(int i = 0; i < (int)s.size(); i ++){
if(s[i] == '('){
st1.push(i);
st2.push(i);
}
else{
if(!st1.empty()){
ret[st1.top()] = 'G';
ret[i] = 'R';
st1.pop();
}
else if(!st2.empty()){
ret[i] = 'B';
st2.pop();
}
else{
cout << "impossible\n";
return;
}
}
}
queue<int> q;
for(int i = (int)s.size() - 1; i >= 0; i --){
if(s[i] == ')'){
q.push(i);
}
else{
if(!st.empty() and !q.empty() and st2.top() == i){
ret[i] = 'B';
st2.pop();
q.pop();
}
else {
ret[i] = 'G';
}
}
}
cout << ret << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
int t_case;
cin >> t_case;
if(t_case == 1){
int t;
cin >> t;
string s;
while(t --){
cin >> s;
solve(s);
}
}
else if(t_case == 2){
int t;
cin >> t;
memset(dp, -1, sizeof dp);
while(t --){
int n;
cin >> n;
cout << rek(n, 0, 0) << endl;
}
}
return 0;
}