Submission #150173

#	Time	Username	Problem	Language	Result	Execution time	Memory
150173		준표야 함수컵은 캐리해줄거지? (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	215 ms	11136 KiB

hiccup

#include "hiccup.h"

#include <cstdio>
#include <algorithm>

using namespace std;

int st[1000006] = {-1};
int top;
bool chk(string &S, int k) {
	top = 0;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'H') {
			st[++top] = -1;
		}
		else if (S[i] == 'C') {
			st[++top] = -2;
		}
		else if (S[i] == '!') {
			if (st[top] < 0) st[++top] = 1;
			else st[top]++;
			if (st[top - 1] == -1) top--;
		}
		if (k) while (top > 2 && st[top - 2] == -1 && st[top - 1] == -2 && st[top] >= k) {
			st[top - 2] = st[top] - k;
			top -= 2;
			while (st[top - 1] >= 0) {
				st[top - 1] += st[top];
				top--;
			}
			while (st[top] == 0) top--;
		}
		else {
			while (st[top] >= 0) top--;
			while (top > 1 && st[top - 1] == -1 && st[top] == -2) {
				top -= 2;
				while (st[top] >= 0) top--;
			}
		}
	}
	return !top;
}


int HicCup(std::string S) {
	int st[1000006] = {0};
	int top = 0;
	if (S[0] != 'H') return -1;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'H') {
			st[top]++;
			st[++top] = 0;
		}
		else if (S[i] == 'C') {
			if (st[top] == 0 && S[i - 1] != 'H') return -1;
			top--;
		}
		if (S[i] == '!' && S[i -1] == 'H') return -1;
		if (top < 0) return -1;
	}
	if (top) return -1;
	int l = 0, r = S.size();
	while (l + 1 < r) {
		int mid = l + r >> 1;
		if (!chk(S, mid)) r = mid;
		else l = mid;
	}
	return l;
}

// int main() {
// 	int ret = HicCup("HHC!!C!");
// 	printf("%d\n", ret);
// }

Compilation message (stderr)

hiccup.cpp: In function 'bool chk(std::__cxx11::string&, int)':
hiccup.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
hiccup.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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