#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define __h 0
#define __hc 1
#define __t 2
int HicCup(std::string s) {
int n = s.size();
int p = 0, q = 0;
for (int i = 0; i < n; i++) {
if (i && s[i - 1] == 'H' && s[i] == '!')
return -1;
if (s[i] == 'H') p++;
if (s[i] == 'C') q++;
}
int r = n - p - q;
if (p != q) return -1;
if (p == 0) return -1;
int R = r / p + 1;
int L = 0;
if (R == 0) {
int u = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'H') u++;
else if (s[i] == 'C'){
if (u > 0) u--;
else return -1;
}
}
return 0;
}
// [L, R)
while (L + 1 < R) {
int M = (L + R) / 2;
int flag = 1;
vector<PII> f;
// cout << "========================== " << M << endl;
for (int i = 0; i < n; i++) {
// cout << i << ' ' << s[i] << endl;
if (s[i] == 'H') f.push_back(PII(__h, 1));
else if (s[i] == 'C') {
while (f.size() && f.back().first == __t) f.pop_back();
if (!f.size() || f.back().first == __hc) {
flag = 0;
goto KKE;
}
f.pop_back();
f.push_back(PII(__hc, 1));
}
else if (s[i] == '!') {
if (f.back().first == __t) f.back().second++;
else f.push_back(PII(__t, 1));
if (f.back().second >= M) {
f.pop_back();
if (f.size()) {
if (f.back().first != __hc) {
}
else {
f.pop_back();
}
}
}
}
// cout << i << ' ' << flag << ' ' << f.size();
// for (auto &x : f)
// cout << " " << x.first << ',' << x.second; cout << endl;
}
// cout << "???" << endl;
while (f.size() && f.back().first == __t) f.pop_back();
// cout << flag << ' ' << f.size() << endl;
if (f.size()) flag = 0;
KKE:
// cout << "flag : " << flag << endl;
if (flag) L = M;
else R = M;
}
return L;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
