# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
61885 | 2018-07-27T04:22:46 Z | ainta(#1792) | parentrises (BOI18_parentrises) | C++11 | 1000 ms | 1264 KB |
#include<cstdio> #include<algorithm> #include<queue> #define N_ 1010000 using namespace std; char p[N_]; int n, S[N_], v[N_]; void Do1() { int i; S[0] = 0; for (i = 0; i < n; i++) { if (p[i] == '(')S[i + 1] = S[i] + 1; else S[i + 1] = S[i] - 1; } int Mn = 0; for (i = 1; i <= n; i++) { if (Mn > S[i]) { Mn = S[i]; v[i-1] = 1; } } int t = S[n] - Mn; for (i = n - 1; i >= 0 && t; i--) { if (p[i] == '(') { t--; v[i] = 1; } } } bool Do2() { int i; queue<int>Q; int s = 0; for (i = 0; i < n; i++) { if (p[i] == '(')s++; if (p[i] == ')')s--; if (!v[i] && p[i] == ')') { Q.push(i); } if (s < 0) { if (Q.empty())return false; v[Q.front()] = 2; Q.pop(); s++; } } for (i = n - 1; i >= 0 && s; i--) { if (!v[i] && p[i] == '(') { s--; v[i] = 2; } } int ss = 0; for (i = 0; i < n; i++) { if (v[i] != 2) { if (p[i] == '(')ss++; else ss--; } if (ss < 0)return false; } if (ss)return false; return true; } void Solve1() { int TC, i; scanf("%d", &TC); while (TC--) { scanf("%s", p); for (i = 0; p[i]; i++)v[i] = 0; n = i; Do1(); if (Do2()) { for (i = 0; i < n; i++) { if (v[i] == 1)printf("R"); else if (v[i] == 2)printf("B"); else printf("G"); } printf("\n"); } else { puts("impossible"); } } } int Mod = 1000000007, D[310][610]; int Calc2(int n, int M) { int i, j; for (i = 0; i <= n; i++) for (j = 0; j <= n + n; j++) D[i][j] = 0; D[0][n] = 1; for (i = 0; i <= n; i++) { for (j = 0; j <= n + n; j++) { int t = j - n; if ((-t) * 3 > i)D[i][j] = 0; t = (j - n) - M; if ((-t) * 3 > (n - i))D[i][j] = 0; if (!D[i][j])continue; D[i + 1][j + 1] = (D[i + 1][j + 1] + D[i][j]) % Mod; D[i + 1][j - 1] = (D[i + 1][j - 1] + D[i][j]) % Mod; } } return D[n][n + M]; } int Calc(int n) { int res = 0; int t = n / 3, i; for (i = -t; i <= t; i++) { res = (res + Calc2(n, i)) % Mod; } return res; } void Solve2() { int i, TC, n; scanf("%d", &TC); while (TC--) { scanf("%d", &n); printf("%d\n", Calc(n)); } } int main() { //freopen("input.txt", "r", stdin); int ck; scanf("%d", &ck); if (ck == 1) { Solve1(); } else { Solve2(); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 484 KB | Output is correct |
3 | Incorrect | 2 ms | 484 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 492 KB | Output is correct |
2 | Incorrect | 3 ms | 536 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 492 KB | Output is correct |
2 | Incorrect | 3 ms | 536 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 492 KB | Output is correct |
2 | Incorrect | 3 ms | 536 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 568 KB | Output is correct |
2 | Correct | 4 ms | 568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 568 KB | Output is correct |
2 | Correct | 4 ms | 568 KB | Output is correct |
3 | Execution timed out | 1082 ms | 1264 KB | Time limit exceeded |