# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
64394 | 2018-08-04T09:35:40 Z | Just_Solve_The_Problem | parentrises (BOI18_parentrises) | C++11 | 163 ms | 13408 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(s) (int)s.size() #define all(s) s.begin(), s.end() const int N = (int)1e6 + 7; const int inf = (int)1e9 + 7; int b[N]; vector < int > stk; int a[N]; int mod = (int)1e9 + 7; bool solve1(string &s) { a[0] = 1; b[0] = ((s[0] == '(') ? 1 : -1); for (int i = 1; i < sz(s); i++) { b[i] = b[i - 1] + ((s[i] == '(') ? 1 : -1); a[i] = 1; } int cur = 0; stk.clear(); for (int i = 0; i < sz(s); i++) { if (s[i] == ')') stk.pb(i); if (b[i] + cur < 0) { // cout << i << ' ' << b[i] + cur << ' ' << sz(stk) << endl; while (b[i] + cur < 0 && sz(stk) > 1) { a[stk.back()] = 0; stk.pop_back(); a[stk.back()] = 2; stk.pop_back(); cur++; } if (b[i] + cur < 0) { return 0; } } } cur = 0; stk.clear(); for (int i = 0; i < sz(s); i++) { s[i] = ((s[i] == '(') ? ')' : '('); } reverse(all(s)); b[0] = ((s[0] == '(') ? 1 : -1); for (int i = 1; i < sz(s); i++) { b[i] = b[i - 1] + ((s[i] == '(') ? 1 : -1); } for (int i = 0; i < sz(s); i++) { if (a[sz(s) - i - 1] == 2) continue; if (s[i] == ')') stk.pb(i); if (b[i] + cur < 0) { // cout << i << ' ' << b[i] + cur << ' ' << sz(stk) << endl; while (b[i] + cur < 0 && sz(stk) > 1) { a[sz(s) - stk.back() - 1] = 0; stk.pop_back(); a[sz(s) - stk.back() - 1] = 2; stk.pop_back(); cur++; } if (b[i] + cur < 0) { return 0; } } } stk.clear(); reverse(all(s)); for (int i = 0; i < sz(s); i++) { s[i] = ((s[i] == '(') ? ')' : '('); } int b1 = 0; int b2 = 0; bool fl = 0; for (int i = 0; i < sz(s); i++) { if (a[i] <= 1) { b1 += ((s[i] == '(') ? 1 : -1); } if (a[i] >= 1) { b2 += ((s[i] == '(') ? 1 : -1); } fl |= (b1 < 0 || b2 < 0); } fl |= (b1 != 0 || b2 != 0); if (fl) { return 0; } return 1; } int n; int add(int a, int b) { return (a + b) % mod; } int dp[2][303][303]; int ans[303]; void solve2() { dp[1][0][0] = 1; for (int i = 0; i <= 300; i++) { for (int j = 0; j <= i; j++) { for (int k = 0; k <= j; k++) { if (j * 2 < i - j) dp[1][j][k] = 0; dp[0][j][k] = dp[1][j][k]; if (k == 0) ans[i] = add(ans[i], dp[0][j][k]); } } memset(dp[1], 0, sizeof dp[1]); for (int j = 0; j <= i; j++) { for (int k = 0; k <= j; k++) { dp[1][j + 1][k + 1] = add(dp[1][j + 1][k + 1], dp[0][j][k]); dp[1][j][max(k - 2, 0)] = add(dp[1][j][max(k - 2, 0)], dp[0][j][k]); } } } } main() { int p = 1; scanf("%d", &p); int test; scanf("%d", &test); if (p == 1) { while (test--) { string s; cin >> s; if (solve1(s) == 0) { puts("impossible"); } else { for (int i = 0; i < sz(s); i++) { if (a[i] == 0) printf("R"); else if (a[i] == 1) printf("G"); else printf("B"); } puts(""); } } } else { solve2(); while (test--) { int x; scanf("%d", &x); printf("%d\n", ans[x]); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 3 ms | 484 KB | Output is correct |
3 | Correct | 2 ms | 484 KB | Output is correct |
4 | Correct | 4 ms | 484 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 3 ms | 560 KB | Output is correct |
4 | Correct | 3 ms | 588 KB | Output is correct |
5 | Correct | 3 ms | 716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 3 ms | 560 KB | Output is correct |
4 | Correct | 3 ms | 588 KB | Output is correct |
5 | Correct | 3 ms | 716 KB | Output is correct |
6 | Correct | 2 ms | 716 KB | Output is correct |
7 | Correct | 3 ms | 716 KB | Output is correct |
8 | Correct | 2 ms | 716 KB | Output is correct |
9 | Correct | 3 ms | 716 KB | Output is correct |
10 | Correct | 3 ms | 716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 3 ms | 560 KB | Output is correct |
4 | Correct | 3 ms | 588 KB | Output is correct |
5 | Correct | 3 ms | 716 KB | Output is correct |
6 | Correct | 2 ms | 716 KB | Output is correct |
7 | Correct | 3 ms | 716 KB | Output is correct |
8 | Correct | 2 ms | 716 KB | Output is correct |
9 | Correct | 3 ms | 716 KB | Output is correct |
10 | Correct | 3 ms | 716 KB | Output is correct |
11 | Correct | 4 ms | 716 KB | Output is correct |
12 | Correct | 4 ms | 724 KB | Output is correct |
13 | Correct | 3 ms | 724 KB | Output is correct |
14 | Correct | 4 ms | 724 KB | Output is correct |
15 | Correct | 5 ms | 752 KB | Output is correct |
16 | Correct | 22 ms | 752 KB | Output is correct |
17 | Correct | 21 ms | 1920 KB | Output is correct |
18 | Correct | 17 ms | 1920 KB | Output is correct |
19 | Correct | 11 ms | 1920 KB | Output is correct |
20 | Correct | 20 ms | 1936 KB | Output is correct |
21 | Correct | 163 ms | 1936 KB | Output is correct |
22 | Correct | 133 ms | 13304 KB | Output is correct |
23 | Correct | 99 ms | 13304 KB | Output is correct |
24 | Correct | 122 ms | 13304 KB | Output is correct |
25 | Correct | 141 ms | 13408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 13408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 13408 KB | Output is correct |
2 | Correct | 62 ms | 13408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 13408 KB | Output is correct |
2 | Correct | 62 ms | 13408 KB | Output is correct |
3 | Correct | 64 ms | 13408 KB | Output is correct |