Submission #149765

#	Time	Username	Problem	Language	Result	Execution time	Memory
149765		dragoon (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	25 ms	3328 KiB

hiccup

#include "hiccup.h"
using namespace std;

int valid(const string& S) {
	int h = 0, th = 0;
	for (char ch : S) {
		if (ch == 'H') h++, th++;
		if (ch == 'C') {
			if (h == 0) return 0;
			h--;
		}
		if (ch == '!') continue;
	}
	return (h == 0 && th > 0);
}

int check(int x, const string& S) {
	int h = 0, sign = 0;
	for (char ch : S) {
		if (ch == 'H') h++;
		else if (ch == 'C') h--, sign += x;
		else {
			sign--;
			if (sign < 0) sign = 0;
		}
	}
	return sign == 0;
}

int HicCup(std::string S) {
	int cntH = 0, cntSign = 0;
	if (!valid(S)) return -1;
	for (char ch : S) cntH += ch == 'H', cntSign += ch == '!';
	int lo = 0, 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: 0 / 76