제출 #148398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148398		Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	31 ms	7296 KiB

hiccup

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

int a[1000000];

bool chk(string &s, int l, int r, int x, int b=0) {
	if(l>r)
		return 1;
	while(s[r]=='!') {
		--r;
		++b;
	}
	b-=x;
	if(b<0)
		return 0;
	return chk(s, a[r]+1, r-1, x)&&chk(s, l, a[r]-1, x, b);
}

int HicCup(string s) {
	int n=s.size();
	//check correctness
	if(s[0]=='!')
		return -1;
	for(int i=0; i+1<n; ++i)
		if(s[i]=='H'&&s[i+1]=='!')
			return -1;
	//bracket matching
	vector<int> t;
	for(int i=0; i<n; ++i) {
		if(s[i]=='H')
			t.push_back(i);
		else if(s[i]=='C') {
			if(t.empty())
				return -1;
			a[i]=t.back();
			t.pop_back();
		}
	}
	if(t.size())
		return -1;
	int lb=0, rb=n;
	while(lb<rb) {
		int mb=(lb+rb+1)/2;
		if(chk(s, 0, n-1, mb))
			lb=mb;
		else
			rb=mb-1;
	}
	return lb;
}

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