답안 #148143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148143	2019-08-31T14:38:47 Z	조팍시\n123(#3740, tlwpdus, ainta, cki86201)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	65 ms	10104 KB

hiccup

#include "hiccup.h"

char p[1010000], q[1010000];
int n, st[1010000], Mat[1010000], K;

bool Good(int b, int e) {
	int i;
	for (i = b; i <= e; i++) {
		if (p[i] == '(') {
			int t = Mat[i];
			if (t != i + 1) {
				if (!Good(i + 1, t - 1))return false;
			}
			i = t;
			continue;
		}
	}
	int cnt = 0;
	for (i = b; i <= e; i++) {
		q[cnt++] = p[i];
		if (p[i] == '(') {
			i = Mat[i];
			q[cnt++] = p[i];
			continue;
		}
	}
	if (q[0] != '(')return false;
	int c = 0;
	for (i = cnt - 1; i >= 0; i--) {
		if (q[i] == '!')c++;
		if (q[i] == ')')c -= K;
		if (c < 0)return false;
	}
	return true;
}

bool OK(int KK) {
	K = KK;
	int i;
	return Good(0, n - 1);
}

int HicCup(std::string S) {
	n = S.size();
	int i, top = 0;
	for (i = 0; i < n; i++) {
		p[i] = S[i];
		if (p[i] == 'H')p[i] = '(';
		if (p[i] == 'C')p[i] = ')';
	}
	for (i = 0; i < n; i++) {
		if (p[i] == '(') {
			st[++top] = i;
		}
		if (p[i] == ')') {
			if (!top)return -1;
			Mat[i] = st[top];
			Mat[st[top]] = i;
			top--;
		}
	}
	if (top)return -1;
	int b = 0, e = n-1, r = -1;
	while (b <= e) {
		int mid = (b + e) >> 1;
		if (OK(mid)) {
			r = mid;
			b = mid + 1;
		}
		else e = mid - 1;
	}
	return r;
}

Compilation message

hiccup.cpp: In function 'bool OK(int)':
hiccup.cpp:39:6: warning: unused variable 'i' [-Wunused-variable]
  int i;
      ^

Subtask #1

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	632 KB	Output is correct
5	Correct	37 ms	9208 KB	Output is correct
6	Correct	15 ms	5240 KB	Output is correct
7	Correct	15 ms	5240 KB	Output is correct
8	Correct	36 ms	9208 KB	Output is correct
9	Correct	38 ms	9184 KB	Output is correct
10	Correct	17 ms	5240 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct

Subtask #2

76.0 / 76.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	632 KB	Output is correct
5	Correct	37 ms	9208 KB	Output is correct
6	Correct	15 ms	5240 KB	Output is correct
7	Correct	15 ms	5240 KB	Output is correct
8	Correct	36 ms	9208 KB	Output is correct
9	Correct	38 ms	9184 KB	Output is correct
10	Correct	17 ms	5240 KB	Output is correct
11	Correct	17 ms	6008 KB	Output is correct
12	Correct	14 ms	6652 KB	Output is correct
13	Correct	11 ms	5496 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	22 ms	9640 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	3 ms	760 KB	Output is correct
19	Correct	34 ms	10104 KB	Output is correct
20	Correct	24 ms	9948 KB	Output is correct
21	Correct	32 ms	7800 KB	Output is correct
22	Correct	45 ms	5780 KB	Output is correct
23	Correct	65 ms	6264 KB	Output is correct
24	Correct	23 ms	9976 KB	Output is correct
25	Correct	39 ms	9264 KB	Output is correct
26	Correct	30 ms	9336 KB	Output is correct
27	Correct	46 ms	8184 KB	Output is correct
28	Correct	58 ms	6392 KB	Output is correct
29	Correct	64 ms	6400 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	5 ms	888 KB	Output is correct
33	Correct	2 ms	376 KB	Output is correct