제출 #150888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150888		kriii	HicCup (FXCUP4_hiccup)	C++17	100 / 100	523 ms	19552 KiB

hiccup

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

int HicCup(std::string S) {
	int N = S.size();
	int l = -1, r = N;
	while (l + 1 < r){
		int m = (l + r) / 2;

		vector<pair<char, int> > u;
		bool good = true;
		for (int i = 0; i < N; i++){
			if (S[i] == 'H'){
				u.push_back({ S[i],1 });
			}
			else if (S[i] == 'C'){
				if (!u.empty() && u.back().first == 0) u.pop_back();
				u.push_back({ S[i],1 });
			}
			else{
				if (!u.empty() && u.back().first == '!'){
					u.back().second++;
				}
				else if (!u.empty() && u.back().first == 0){
					u.back().second++;
				}
				else{
					u.push_back({ '!',1 });
				}
			}

			while (1){
				int z = u.size();
				if (m == 0){
					if (z >= 2 && u[z - 2].first == 'H' && u[z - 1].first == 'C'){
						u.pop_back();
						u.pop_back();
						if (!u.empty() && u.back().first == 0);
						else u.push_back({ 0,0 });
					}
					else break;
				}
				else{
					if (z >= 3 && u[z - 3].first == 'H' && u[z - 2].first == 'C' && u[z - 1].first == '!' && u[z - 1].second >= m){
						u.pop_back();
						u.pop_back();
						u.pop_back();
						if (!u.empty() && u.back().first == 0);
						else u.push_back({ 0,0 });
					}
					else if (z >= 3 && u[z - 3].first == 'H' && u[z - 2].first == 'C' && u[z - 1].first == 0 && u[z - 1].second >= m){
						u.pop_back();
						u.pop_back();
						u.pop_back();
						if (!u.empty() && u.back().first == 0);
						else u.push_back({ 0,0 });
					}
					else if (z >= 4 && u[z - 4].first == 'H' && u[z - 3].first == 'C' && u[z - 2].first == 0 && u[z - 1].first == '!' && u[z - 2].second + u[z - 1].second >= m){
						int r = u[z - 2].second + u[z - 1].second - m;
						u.pop_back();
						u.pop_back();
						u.pop_back();
						u.pop_back();
						if (!u.empty() && u.back().second == 0) u.back().second += r;
						else u.push_back({ 0,r });
					}
					else if (z >= 4 && u[z - 4].first == 'H' && u[z - 3].first == 'C' && u[z - 2].first == '!' && u[z - 1].first == 0 && u[z - 2].second + u[z - 1].second >= m){
						int r = u[z - 2].second + u[z - 1].second - m;
						u.pop_back();
						u.pop_back();
						u.pop_back();
						u.pop_back();
						if (!u.empty() && u.back().second == 0) u.back().second += r;
						else u.push_back({ 0,r });
					}
					else break;
				}

				while (u.size() >= 2){
					z = u.size();
					if (u[z - 2].first == 0 && (u[z - 1].first == '!' || u[z - 1].first == 0)){
						u[z - 2].second += u[z - 1].second;
						u.pop_back();
					}
					else break;
				}
			}
		}

		while (!u.empty() && u.back().first == 0) u.pop_back();
		if (!u.empty()) good = false;

		if (good) l = m;
		else r = m;
	}
	return l;
}

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