| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 150410 | Torat (#200) | HicCup (FXCUP4_hiccup) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//~ #include "hiccup.h"
#include "grader.cpp"
using namespace std;
const int N = 1000001;
int n;
string s;
vector <int> h;
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;
}
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);
}
vector <int> exs(n), cs(n);
int ans = n;
for(int i = n - 1 ; i >= 0 ; i--){
if(s[i] == '!') exs[h[i]]++;
else if(s[i] == 'C'){
cs[h[i]]++;
ans = min(ans, exs[h[i]] / cs[h[i]]);
}
}
return ans;
}