제출 #148911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148911		1 WA = 5 Push Up (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	86 ms	8832 KiB

hiccup

#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;

int N;
std::string S;
int myS[1000010];

int top;
int state[1000010];

bool able(int v)
{
	top = 0;
	for (int i = 0; i < N; i++)
	{
		top++;
		if (S[i] == 'H')
			state[top] = 1;
		if (S[i] == 'C')
		{
			if (state[top - 1] == 1)
				state[top] = 2;
			else return false;
		}
		if (S[i] == '!')
		{
			if (state[top - 1] <= 1) top--;
			else state[top] = state[top - 1] + 1;
		}

		if (state[top] == v + 2)
			top -= v + 2;
	}

	return state[top] == 0;
}

int HicCup(std::string S_) {
	S = S_;
	N = S.size();

	stack <int> ST;
	for (int i = 0; i < N; i++)
	{
		if (S[i] == 'H') ST.push(i);
		if (S[i] == 'C')
		{
			if (ST.empty()) return -1;
			myS[ST.top()] = i;
			ST.pop();
		}
	}
	if (!ST.empty()) return -1;

	for (int i = 0; i < N; i++)
		if (S[i] == '!')
		{
			if (i == 0) return -1;
			if (S[i - 1] == 'H') return -1;
		}

	int s, e, v;
	s = 0; e = (1 << 20) - 1;
	while (s < e)
	{
		v = (s + e) / 2;
		if (able(v + 1)) s = v + 1;
		else e = v;
	}

	return s;
}

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