#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;
string S;
int H[1000010];
int lc[1000010];
bool f(int s, int e, int k, int x) {
if(s > e) return true;
if(lc[e] < s) return false;
for(int i = lc[e] + 1; i <= e; i++) if(S[i] == '!') k++;
if(k < x) return false;
return f(s, H[lc[e]] - 1, k - x, x) && f(H[lc[e]] + 1, lc[e] - 1, 0, x);
}
int HicCup(string SS) {
S = SS;
int N = S.size();
int sum = 0;
for(int i = 0; i < S.size(); i++) {
if(S[i] == 'H') sum++;
else if(S[i] == 'C') sum--;
if(sum < 0) return -1;
}
if(sum != 0) return -1;
int fc = S.size();
for(int i = S.size() - 1; i >= 0; i--) if(S[i] == 'C') fc = i;
if(fc == S.size()) return -1;
for(int i = 0; i < fc; i++) if(S[i] == '!') return -1;
stack<int> st;
for(int i = 0; i < S.size(); i++) {
if(S[i] == 'H') st.push(i);
else if(S[i] == 'C') {
H[i] = st.top();
st.pop();
}
}
int t = -1;
for(int i = 0; i < S.size(); i++) {
if(S[i] == 'C') t = i;
lc[i] = t;
}
//for(int i = 0; i < S.size(); i++) printf("%d ", H[i]);
//printf("\n");
int s = -1, e = S.size();
while(s < e) {
int m = (s + e + 1) / 2;
int cnt = 0;
if(f(0, S.size() - 1, 0, m)) s = m;
else e = m - 1;
}
return s;
}
Compilation message
hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
hiccup.cpp:29:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(fc == S.size()) return -1;
~~~^~~~~~~~~~~
hiccup.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
hiccup.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
hiccup.cpp:53:7: warning: unused variable 'cnt' [-Wunused-variable]
int cnt = 0;
^~~
hiccup.cpp:19:6: warning: unused variable 'N' [-Wunused-variable]
int N = S.size();
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
768 KB |
Output is correct |
| 5 |
Correct |
45 ms |
12280 KB |
Output is correct |
| 6 |
Correct |
14 ms |
4352 KB |
Output is correct |
| 7 |
Correct |
14 ms |
4352 KB |
Output is correct |
| 8 |
Correct |
42 ms |
12280 KB |
Output is correct |
| 9 |
Correct |
43 ms |
12160 KB |
Output is correct |
| 10 |
Correct |
14 ms |
4224 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
768 KB |
Output is correct |
| 5 |
Correct |
45 ms |
12280 KB |
Output is correct |
| 6 |
Correct |
14 ms |
4352 KB |
Output is correct |
| 7 |
Correct |
14 ms |
4352 KB |
Output is correct |
| 8 |
Correct |
42 ms |
12280 KB |
Output is correct |
| 9 |
Correct |
43 ms |
12160 KB |
Output is correct |
| 10 |
Correct |
14 ms |
4224 KB |
Output is correct |
| 11 |
Correct |
16 ms |
4352 KB |
Output is correct |
| 12 |
Correct |
15 ms |
4352 KB |
Output is correct |
| 13 |
Correct |
13 ms |
4224 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
36 ms |
12544 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
6 ms |
640 KB |
Output is correct |
| 19 |
Correct |
29 ms |
12160 KB |
Output is correct |
| 20 |
Correct |
35 ms |
12672 KB |
Output is correct |
| 21 |
Correct |
34 ms |
9856 KB |
Output is correct |
| 22 |
Correct |
30 ms |
7680 KB |
Output is correct |
| 23 |
Correct |
38 ms |
8192 KB |
Output is correct |
| 24 |
Correct |
40 ms |
12928 KB |
Output is correct |
| 25 |
Correct |
42 ms |
12408 KB |
Output is correct |
| 26 |
Correct |
33 ms |
13184 KB |
Output is correct |
| 27 |
Correct |
26 ms |
10240 KB |
Output is correct |
| 28 |
Correct |
29 ms |
8448 KB |
Output is correct |
| 29 |
Correct |
35 ms |
8312 KB |
Output is correct |
| 30 |
Correct |
5 ms |
384 KB |
Output is correct |
| 31 |
Correct |
5 ms |
384 KB |
Output is correct |
| 32 |
Correct |
7 ms |
1024 KB |
Output is correct |
| 33 |
Correct |
5 ms |
384 KB |
Output is correct |
