Submission #149171

#	Time	Username	Problem	Language	Result	Execution time	Memory
149171		본인 방금 올솔하는 상상함 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	268 ms	15104 KiB

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 (stderr)

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 / 24
• Subtask 2: 76 / 76