Submission #613140

#	Time	Username	Problem	Language	Result	Execution time	Memory
613140		ajpiano	HicCup (FXCUP4_hiccup)	C++17	100 / 100	195 ms	3648 KiB

hiccup

#include <bits/stdc++.h>
#include "hiccup.h"

using namespace std;

#define f first
#define s second

int HicCup(std::string S) {
	int N = S.size();
	int hbef = 0;
	for(int i = 0; i < N; i++){
		if(S[i] == '!'){
			if(i == 0 || S[i-1] == 'H') return -1;
		}
		else if(S[i] == 'H') hbef++;
		else{
			hbef--;
			if(hbef < 0) return -1;
		}
	}
	if(hbef != 0) return -1;

	int l = 0, r = 1000000;

	while(r-l > 1){
		int mid = (l+r)>>1;
		vector<pair<int,bool>> stk; //! points. Complete
		bool good = 1;
		for(int i = 0; i < N; i++){
			if(S[i] == 'H'){
				stk.push_back({0,0});
			}else if(S[i] == 'C'){
				while(stk.back().s == 1){
					if(stk.back().f < mid) good = 0;
					stk.pop_back();
				}
				stk.back().s = 1;
			}else{
				if(stk.empty() || stk.back().s == 0) continue;
				else stk.back().f++;
				if(stk.back().f >= mid) stk.pop_back();
			}
		}

		for(auto &a: stk){
			if(a.f < mid) good = 0;
		}

		if(good) l = mid;
		else r = mid;
	}

	return l;
}

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