답안 #149171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149171	2019-09-01T05:52:50 Z	본인 방금 올솔하는 상상함(#3610, gs18113, dennisstar, red1108)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	268 ms	15104 KB

hiccup

#include "hiccup.h"
#include<bits/stdc++.h>
#define N 1000005

using namespace std;
typedef pair<int,int> pi;

int cnt[N];
int ch[N];
int nxt[N];
int asdf[N];

int HicCup(std::string S) {
	int n = S.size();
	stack<pi> st;
	stack<pi> st2;
	int lv=0;
	for(int i=0;i<n;i++){
		if(S[i]=='H'){
			lv++;
			st.push(pi(i, lv));
			st2.push(pi(i, lv));
		}
		else if(S[i]=='C'){
			if(st.empty()) return -1;
			pi t=st.top();
			st.pop();
			while(!st2.empty()&&(st2.top().second>lv||st2.top()==t)){
				st2.pop();
			}
			if(!st2.empty()&&st2.top().second==lv) {
				nxt[st2.top().first]=t.first+1;
				st2.pop();
			}
			st2.push(t);
			lv--;
		}
		else{
			if(st2.empty()||lv==st2.top().second){
				return -1;
			}
			cnt[st2.top().first]++;
		}
	}
	if(!st.empty()) return -1;
	int ans=INT_MAX;
	int s=0, e=n;
	int sum;
	while(s<e){
		int m=s+e+1>>1;
		int flag=1;
		for(int i=0;i<n;i++) ch[i]=0;
		for(int i=0;i<n;i++){
			if(ch[i]) continue;
			if(S[i]!='H') continue;
			else{
				sum=0;
				for(int j=i+1;j;j=nxt[j-1]){
					ch[j-1]=1;
					if(sum+m>cnt[j-1]){
						sum=sum+m-cnt[j-1];
					}
					else{
						sum=0;
					}
				}
				if(sum>0) flag=0;
			}
		}
		if(flag) s=m;
		else e=m-1;
	}
	return s;
}

Compilation message

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e+1>>1;
         ~~~^~
hiccup.cpp:46:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans=INT_MAX;
      ^~~

Subtask #1

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	384 KB	Output is correct
2	Correct	7 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	11 ms	768 KB	Output is correct
5	Correct	268 ms	11128 KB	Output is correct
6	Correct	13 ms	3328 KB	Output is correct
7	Correct	13 ms	3328 KB	Output is correct
8	Correct	251 ms	11128 KB	Output is correct
9	Correct	256 ms	11128 KB	Output is correct
10	Correct	12 ms	3328 KB	Output is correct
11	Correct	6 ms	384 KB	Output is correct

Subtask #2

76.0 / 76.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	384 KB	Output is correct
2	Correct	7 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	11 ms	768 KB	Output is correct
5	Correct	268 ms	11128 KB	Output is correct
6	Correct	13 ms	3328 KB	Output is correct
7	Correct	13 ms	3328 KB	Output is correct
8	Correct	251 ms	11128 KB	Output is correct
9	Correct	256 ms	11128 KB	Output is correct
10	Correct	12 ms	3328 KB	Output is correct
11	Correct	17 ms	4864 KB	Output is correct
12	Correct	18 ms	6016 KB	Output is correct
13	Correct	15 ms	3712 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	12 ms	3456 KB	Output is correct
16	Correct	5 ms	256 KB	Output is correct
17	Correct	6 ms	384 KB	Output is correct
18	Correct	6 ms	768 KB	Output is correct
19	Correct	78 ms	14992 KB	Output is correct
20	Correct	107 ms	15096 KB	Output is correct
21	Correct	67 ms	10496 KB	Output is correct
22	Correct	59 ms	6912 KB	Output is correct
23	Correct	57 ms	7296 KB	Output is correct
24	Correct	109 ms	15104 KB	Output is correct
25	Correct	212 ms	15096 KB	Output is correct
26	Correct	128 ms	15060 KB	Output is correct
27	Correct	71 ms	11264 KB	Output is correct
28	Correct	61 ms	7680 KB	Output is correct
29	Correct	56 ms	7296 KB	Output is correct
30	Correct	6 ms	384 KB	Output is correct
31	Correct	5 ms	384 KB	Output is correct
32	Correct	9 ms	1024 KB	Output is correct
33	Correct	6 ms	384 KB	Output is correct