Submission #149747

#	Time	Username	Problem	Language	Result	Execution time	Memory
149747		강한친구 대한육군 (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	1068 ms	262144 KiB

hiccup

#include "hiccup.h"
static bool able(int& dep, std::string a, int x);
static bool dfs(int &dep, std::string a, int x, int state)
{
	//printf("%d %d %d ", dep, x, state);
	//if (dep < a.size())printf("%c", a[dep]);
	//else printf("\\");
	//printf("\n");
	if (dep == a.size())return (state == (x+2));
	if (state == x + 2)
	{
		return true;
	}
	if (state == 1) {
		while (a[dep] != 'C')
		{
			if (a[dep] == 'H')
			{
				if (!able(dep, a, x))
					return false;
			}
			else
			{
				dep++;
			}
		}
		if (a[dep] == 'C') {
			dep++;
			return dfs(dep, a, x, 2);
		}
	}
	else {
		while (a[dep] != '!')
		{
			if (a[dep] == 'H')
			{
				if (!able(dep, a, x))
					return false;
			}
			else
				return false;
		}
		if (a[dep] == '!')
		{
			dep++;
			return dfs(dep, a, x, state + 1);
		}
	}
}
static bool able(int& dep, std::string a, int x)
{
	//printf("-cur dep : %d\n", dep);
	if (a[dep] == 'H')
	{
		dep++;
		if (!dfs(dep, a, x, 1))
			return false;
	}
	else if (a[dep] == 'C')
	{
		return false;
	}
	return true;
}
static bool able2(int &dep, std::string a, int x)
{
	while (dep < a.size())
	{
		//printf("cur dep : %d\n", dep);
		if (a[dep] == 'H')
		{
			dep++;
			if (!dfs(dep, a, x, 1))
				return false;
		}
		else if(a[dep] == 'C')
			return false;
		else {
			dep++;
		}
	}
	return true;
}
int HicCup(std::string a) {
	int n = a.size();
	int i, j, k;
	for (i = j=k=0; i < n; i++) {
		if (a[i] == 'H') {
			k++; j = 0;
		}
		else if (a[i] == 'C') { k--; j = 1; if (k < 0)return -1; }
		else {
			if (j == 0)return -1;
		}
	}
	if (k > 0) return -1;
	int l = 1;
	int r = n;

	while (l < r) {
		int mid = (l + r) / 2;
		int dep = 0;
		//printf("try %d\n", mid);
		if (able2(dep, a, mid))
		{
			l = mid + 1;
		}
		else
			r = mid;
	}

	return l-1;
}

Compilation message (stderr)

hiccup.cpp: In function 'bool dfs(int&, std::__cxx11::string, int, int)':
hiccup.cpp:9:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (dep == a.size())return (state == (x+2));
      ~~~~^~~~~~~~~~~
hiccup.cpp: In function 'bool able2(int&, std::__cxx11::string, int)':
hiccup.cpp:67:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (dep < a.size())
         ~~~~^~~~~~~~~~
hiccup.cpp: In function 'bool dfs(int&, std::__cxx11::string, int, int)':
hiccup.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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