Submission #149638

#	Time	Username	Problem	Language	Result	Execution time	Memory
149638		잉여로운 고3 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	45 ms	13184 KiB

hiccup

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

string S;
int H[1000010];
int lc[1000010];

bool f(int s, int e, int k, int x) {
	if(s > e) return true;
	if(lc[e] < s) return false;
	for(int i = lc[e] + 1; i <= e; i++) if(S[i] == '!') k++;
	if(k < x) return false;
	return f(s, H[lc[e]] - 1, k - x, x) && f(H[lc[e]] + 1, lc[e] - 1, 0, x);
}

int HicCup(string SS) {
	S = SS;
	int N = S.size();
	int sum = 0;
	for(int i = 0; i < S.size(); i++) {
		if(S[i] == 'H') sum++;
		else if(S[i] == 'C') sum--;
		if(sum < 0) return -1;
	}
	if(sum != 0) return -1;
	int fc = S.size();
	for(int i = S.size() - 1; i >= 0; i--) if(S[i] == 'C') fc = i;
	if(fc == S.size()) return -1;
	for(int i = 0; i < fc; i++) if(S[i] == '!') return -1;

	stack<int> st;
	for(int i = 0; i < S.size(); i++) {
		if(S[i] == 'H') st.push(i);
		else if(S[i] == 'C') {
			H[i] = st.top();
			st.pop();
		}
	}

	int t = -1;
	for(int i = 0; i < S.size(); i++) {
		if(S[i] == 'C') t = i;
		lc[i] = t;
	}

	//for(int i = 0; i < S.size(); i++) printf("%d ", H[i]);
	//printf("\n");

	int s = -1, e = S.size();
	while(s < e) {
		int m = (s + e + 1) / 2;
		int cnt = 0;
		if(f(0, S.size() - 1, 0, m)) s = m;
		else e = m - 1;
	}
	return s;
}

Compilation message (stderr)

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++) {
                 ~~^~~~~~~~~~
hiccup.cpp:29:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(fc == S.size()) return -1;
     ~~~^~~~~~~~~~~
hiccup.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++) {
                 ~~^~~~~~~~~~
hiccup.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++) {
                 ~~^~~~~~~~~~
hiccup.cpp:53:7: warning: unused variable 'cnt' [-Wunused-variable]
   int cnt = 0;
       ^~~
hiccup.cpp:19:6: warning: unused variable 'N' [-Wunused-variable]
  int N = S.size();
      ^

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