제출 #149584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149584		잉여로운 고3 (#200)	HicCup (FXCUP4_hiccup)	C++17	0 / 100	1100 ms	8312 KiB

hiccup

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

string S;
int H[1000010];

bool f(int s, int e, int k, int x) {
	if(s > e) return true;
	int lc = s - 1;
	for(int i = s; i <= e; i++) if(S[i] == 'C') lc = i;
	if(lc == s - 1) return -1;
	for(int i = lc + 1; i <= e; i++) if(S[i] == '!') k++;
	if(k < x) return false;
	return f(s, H[lc] - 1, k - x, x) && f(H[lc] + 1, lc - 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 s = -1, e = S.size() - 1;
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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