#include "hiccup.h"
char p[1010000], q[1010000];
int n, st[1010000], Mat[1010000], K;
bool Good(int b, int e) {
int i;
for (i = b; i <= e; i++) {
if (p[i] == '(') {
int t = Mat[i];
if (t != i + 1) {
if (!Good(i + 1, t - 1))return false;
}
i = t;
continue;
}
}
int cnt = 0;
for (i = b; i <= e; i++) {
q[cnt++] = p[i];
if (p[i] == '(') {
i = Mat[i];
q[cnt++] = p[i];
continue;
}
}
if (q[0] != '(')return false;
int c = 0;
for (i = cnt - 1; i >= 0; i--) {
if (q[i] == '!')c++;
if (q[i] == ')')c -= K;
if (c < 0)return false;
}
return true;
}
bool OK(int KK) {
K = KK;
int i;
return Good(0, n - 1);
}
int HicCup(std::string S) {
n = S.size();
int i, top = 0;
for (i = 0; i < n; i++) {
p[i] = S[i];
if (p[i] == 'H')p[i] = '(';
if (p[i] == 'C')p[i] = ')';
}
for (i = 0; i < n; i++) {
if (p[i] == '(') {
st[++top] = i;
}
if (p[i] == ')') {
if (!top)return -1;
Mat[i] = st[top];
Mat[st[top]] = i;
top--;
}
}
if (top)return -1;
int b = 0, e = n-1, r = -1;
while (b <= e) {
int mid = (b + e) >> 1;
if (OK(mid)) {
r = mid;
b = mid + 1;
}
else e = mid - 1;
}
return r;
}
Compilation message
hiccup.cpp: In function 'bool OK(int)':
hiccup.cpp:39:6: warning: unused variable 'i' [-Wunused-variable]
int i;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
632 KB |
Output is correct |
| 5 |
Correct |
37 ms |
9208 KB |
Output is correct |
| 6 |
Correct |
15 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
15 ms |
5240 KB |
Output is correct |
| 8 |
Correct |
36 ms |
9208 KB |
Output is correct |
| 9 |
Correct |
38 ms |
9184 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
632 KB |
Output is correct |
| 5 |
Correct |
37 ms |
9208 KB |
Output is correct |
| 6 |
Correct |
15 ms |
5240 KB |
Output is correct |
| 7 |
Correct |
15 ms |
5240 KB |
Output is correct |
| 8 |
Correct |
36 ms |
9208 KB |
Output is correct |
| 9 |
Correct |
38 ms |
9184 KB |
Output is correct |
| 10 |
Correct |
17 ms |
5240 KB |
Output is correct |
| 11 |
Correct |
17 ms |
6008 KB |
Output is correct |
| 12 |
Correct |
14 ms |
6652 KB |
Output is correct |
| 13 |
Correct |
11 ms |
5496 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
22 ms |
9640 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
760 KB |
Output is correct |
| 19 |
Correct |
34 ms |
10104 KB |
Output is correct |
| 20 |
Correct |
24 ms |
9948 KB |
Output is correct |
| 21 |
Correct |
32 ms |
7800 KB |
Output is correct |
| 22 |
Correct |
45 ms |
5780 KB |
Output is correct |
| 23 |
Correct |
65 ms |
6264 KB |
Output is correct |
| 24 |
Correct |
23 ms |
9976 KB |
Output is correct |
| 25 |
Correct |
39 ms |
9264 KB |
Output is correct |
| 26 |
Correct |
30 ms |
9336 KB |
Output is correct |
| 27 |
Correct |
46 ms |
8184 KB |
Output is correct |
| 28 |
Correct |
58 ms |
6392 KB |
Output is correct |
| 29 |
Correct |
64 ms |
6400 KB |
Output is correct |
| 30 |
Correct |
2 ms |
376 KB |
Output is correct |
| 31 |
Correct |
2 ms |
376 KB |
Output is correct |
| 32 |
Correct |
5 ms |
888 KB |
Output is correct |
| 33 |
Correct |
2 ms |
376 KB |
Output is correct |
