Submission #149505

#	Time	Username	Problem	Language	Result	Execution time	Memory
149505		갓띵건 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	36 ms	3328 KiB

hiccup

#include "hiccup.h"
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
typedef pair <int, int> pii;

int HicCup(string s) {
	int n = s.size();
	int h = 0, hc = 0;
	bool flag = false, flag2 = false;
	for(int i = 0; i < n; i++) {
		if(s[i] == 'H') {
			flag2 = true;
			h++;
			flag = false;
		}
		if(s[i] == 'C') {
			h--;
			hc++;
			flag = false;
			flag2 = false;
		}
		if(s[i] == '!' && !flag) {
			if(hc == 0) return -1;
			if(flag2) return -1;
			hc--;
			flag = true;
		}
		if(h < 0) return -1;
	}
	if(h != 0) return -1;
	
	int lb = 0, ub = 1000000;
	while(lb < ub) {
		int m = (lb + ub + 1) / 2;
		vector <pii> v;
		stack <int> H;
		for(int i = 0; i < n; i++) {
			if(s[i] == '!' && !v.empty()) {
				v[v.size()-1].se++;
				while(v[v.size()-1].se < m && i < n - 1 && s[i+1] == '!') {
					i++, v[v.size()-1].se++;
				}
				if(v[v.size()-1].se == m) v.pop_back();
				continue;
			}
			if(s[i] == 'C') {
				bool flag = false;
				while(!v.empty() && H.top() < v[v.size()-1].fi) {
					if(v[v.size()-1].se < m) flag = true;
					v.pop_back();
				}
				v.emplace_back(H.top(), 0);
				if(flag) break;
				H.pop();
			}
			if(s[i] == 'H') H.push(i);
			while(!v.empty() && v[v.size()-1].se >= m) v.pop_back();
		}
		if(v.empty()) lb = m;
		else ub = m-1;
	}
	return lb;
}

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