#include <bits/stdc++.h>
#include "hiccup.h"
//~ #include "grader.cpp"
using namespace std;
const int N = 1000001;
int n;
string s;
vector <int> h;
deque <int> g[N];
bool valid(){
int o = 0;
for(auto &i : s){
o += i == 'H';
o -= i == 'C';
if(o < 0) return 0;
}
if(o) return 0;
for(auto &i : s){
if(i == 'H') o = 0;
else if(i == 'C') o = 1;
else if(o == 0) return 0;
}
return 1;
}
bool check(int x){
for(int i = 0 ; i < N ; i++){
while(g[i].size()) g[i].pop_back();
}
for(int i = n - 1 ; i >= 0 ; i--){
if(s[i] == '!'){
g[h[i]].push_back(i);
}
if(s[i] == 'C'){
int cur = x;
while(cur > 0 && g[h[i]].size()){
g[h[i]].pop_front();
cur--;
}
if(cur) return 0;
}
}
return 1;
}
int HicCup(std::string S) {
s = S;
n = s.size();
if(!valid() || s == string(n, '!')) return -1;
h.resize(n);
h[0] = 1;
for(int i = 1 ; i < n ; i++){
h[i] = h[i - 1];
if(s[i] == 'H') h[i]++;
else if(s[i] == 'C') h[i]--;
//~ else v[h[i]].push_back(i);
}
int l = 0, r = n;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid)) l = mid + 1;
else r = mid - 1;
}
return l - 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
804 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
804 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
