// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 310, maxn2 = 1e6 + 10, mod = 1e9 + 7;
int dp[maxn][2 * maxn][maxn]; // n // 2o - c // o - 2c
int ans[maxn];
void add(int &A, int B){
A = (A + B) % mod;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int P, q;
cin >> P >> q;
if(P == 1){
while(q--){
string s;
cin >> s;
int A = 0;
bool bad = 0;
for(int i = sz(s)-1; i >= 0; i--){
A+= (s[i] == ')' ? 2 : -1);
bad|= A < 0;
}
A = 0;
for(int i = 0; i < sz(s); i++){
A+= (s[i] == '(' ? 2 : -1);
bad|= A < 0;
}
if(bad){
cout << "impossible\n";
continue;
}
int pos = sz(s) - A;
string ans = s;
bool o = 0;
for(int i = 0; i < pos; i++){
if(s[i] == '(')
ans[i] = 'G';
else
ans[i] = (o ? 'R' : 'B'), o^=1;
}
o = 0;
for(int i = sz(s)-1; i >= pos; i--){
if(s[i] == ')')
ans[i] = 'G';
else
ans[i] = (o ? 'R' : 'B'), o^=1;
}
cout << ans << "\n";
}
}
if(P == 2){
dp[0][0][0] = 1;
for(int n = 0; n < maxn - 5; n++){
for(int sm = 0; sm <= 2 * n; sm++){
for(int mx = 0; mx <= n; mx++){
add(dp[n + 1][sm + 2][max(int(0), mx + 1)], dp[n][sm][mx]);
if(sm > 0)
add(dp[n+1][sm - 1][max(int(0), mx - 2)], dp[n][sm][mx]);
}
add(ans[n], dp[n][sm][0]);
}
}
while(q--){
int n;
cin >> n;
cout << ans[n] << "\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
400 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
400 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
400 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
416 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
768 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
640 KB |
Output is correct |
20 |
Correct |
2 ms |
768 KB |
Output is correct |
21 |
Correct |
28 ms |
2172 KB |
Output is correct |
22 |
Correct |
15 ms |
4380 KB |
Output is correct |
23 |
Correct |
11 ms |
2284 KB |
Output is correct |
24 |
Correct |
15 ms |
2772 KB |
Output is correct |
25 |
Correct |
16 ms |
4372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
220 ms |
115192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
220 ms |
115192 KB |
Output is correct |
2 |
Correct |
160 ms |
115192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
220 ms |
115192 KB |
Output is correct |
2 |
Correct |
160 ms |
115192 KB |
Output is correct |
3 |
Correct |
162 ms |
115168 KB |
Output is correct |