Submission #149320

#	Time	Username	Problem	Language	Result	Execution time	Memory
149320		20190901 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	441 ms	20416 KiB

hiccup

#include "hiccup.h"
#include <vector>

using namespace std;


bool Check(string str, int mid)
{
	vector<pair<char, int>> stk;

	int hCnt = 0;
	int cCnt = 0;
	bool isMake = false;
	for (int i = 0; i < str.size(); i++)
	{
		if (stk.empty() && str[i] != '!')
			isMake = false;

		if (str[i] == 'H')
		{
			stk.push_back({ 'H', -1 });
			hCnt++;
		}
		else if (str[i] == 'C')
		{
			if (hCnt > cCnt)
				stk.push_back({ 'C', 0 });
			else
				return false;
			cCnt++;
		}
		else
		{
			if (stk.empty())
			{
				if (isMake)
					continue;
				else
					return false;
			}
			if (stk.back().first == 'H')
			{
				if (isMake)
					continue;
				else
					return false;
			}

			stk.push_back({ '!', stk.back().second + 1 });
		}

		if (stk.back().second == mid)
		{
			for (int i = 0; i < mid + 2; i++)
			{
				if (stk.empty())
					return false;

				if (stk.back().first == 'C')
					cCnt--;
				else if (stk.back().first == 'H')
					hCnt--;
				stk.pop_back();
			}
			isMake = true;
		}
	}

	for (int i = 0; i < stk.size(); i++)
	{
		if (stk[i].first != '!')
			return false;
	}
	return true;
}

int HicCup(string S)
{
	int lo = -1;
	int hi = (int)S.size();


	while (lo + 1 < hi)
	{
		int mid = (lo + hi) >> 1;
		if (Check(S, mid))
		{
			lo = mid;
		}
		else
		{
			hi = mid;
		}
	}

	return lo;
}

Compilation message (stderr)

hiccup.cpp: In function 'bool Check(std::__cxx11::string, int)':
hiccup.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < str.size(); i++)
                  ~~^~~~~~~~~~~~
hiccup.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < stk.size(); i++)
                  ~~^~~~~~~~~~~~

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