Submission #150128

#	Time	Username	Problem	Language	Result	Execution time	Memory
150128		dragoon (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	73 ms	3384 KiB

hiccup

#include "hiccup.h"
#include <stack>
using namespace std;

struct State {
	int cur_state = 0;
	int want = 0;
	int closed = 0;
	// 0 = need C, 1 = need !
	int update(char ch) {
		if (ch == 'C' && cur_state == 0) {
			cur_state = 1;
			return 1;
		}
		if (ch == '!' && cur_state == 1) {
			want--;
			return 1;
		}
		return 0;
	}
};
int check(int x, const string& S) {
	if (x == -1) return 1;
	stack<State> ST;
	int closed = 0;
	for (char ch : S) {
		//printf("processing %d, %c\n", x, ch);
		if (ch == 'H') {
			ST.push(State());
			ST.top().want = x;
			continue;
		}
		else if (ch == 'C') {
			if (ST.empty()) return 0;
			if (!ST.top().update(ch)) return 0;
			if (ST.top().want == 0) {
				ST.pop();
				if (ST.empty()) closed = 1;
				else ST.top().closed = 1;
				//printf("Popped\n");
			}
		}
		else {
			if (ST.empty() && !closed) return 0;
			if (ST.empty() && closed) {
				//printf("consumed\n");
				continue;
			}
			if (!ST.top().update(ch)) {
				if (ST.top().closed) {
					//printf("consumed\n");
					continue;
				}
				return 0;
			}
			if (ST.top().want == 0) {
				ST.pop();
				if (ST.empty()) closed = 1;
				else ST.top().closed = 1;
				//printf("Popped\n");
			}
		}
	}
	return ST.empty();
}

int HicCup(std::string S) {
	int cntH = 0, cntSign = 0;
	for (char ch : S) cntH += ch == 'H', cntSign += ch == '!';
	int lo = -1, hi = cntSign/cntH;
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
		if (check(mid, S)) lo = mid;
		else hi = mid - 1;
	}
	
	return lo;
}

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