Submission #149594

#	Time	Username	Problem	Language	Result	Execution time	Memory
149594		etyu (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	86 ms	4352 KiB

hiccup

#include "hiccup.h"
#include <vector>

std::string s;
int N;
std::vector<int> st;

bool ps(int l)
{
	st.clear();
	for (int i = 0; i < N; i++) {
		if (s[i] == 'H') st.push_back(-1);
		else if (s[i] == 'C') {
			if (st.back() != -1) return false;
			st.back() = 0;
			if (l == 0) st.pop_back();
		}
		else {
			if (st.empty() || st.back() == -1) continue;
			st.back()++;
			if (st.back() >= l) st.pop_back();
		}
	}
	return st.empty();
}

int bs(int s, int e)
{
	int md = (s + e + 1) / 2;
	if (s >= e) return md;
	if (ps(md)) return bs(md, e);
	else return bs(s, md - 1);
}

int HicCup(std::string S) {
	N = S.size();
	s = S;
	int c = 0;
	bool f = false;
	for (int i = 0; i < N; i++) {
		if (S[i] == 'H') {
			f = false; c++;
		}
		else if (S[i] == 'C') {
			f = true; c--;
		}
		else if (!f) return -1;
		if (c < 0) return -1;
	}
	if (c != 0) return -1;
	return bs(0, N);
	return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 76 / 76