Submission #149256

#	Time	Username	Problem	Language	Result	Execution time	Memory
149256		TeamSUA (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	27 ms	3376 KiB

hiccup

#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;
	
		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;
			}
		}
		
	// [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.size() && 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) {
							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;
}

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