Submission #147986

#	Time	Username	Problem	Language	Result	Execution time	Memory
147986		imsifile	HicCup (FXCUP4_hiccup)	C++17	100 / 100	64 ms	4288 KiB

hiccup

#include "hiccup.h"
using namespace std;
 
char ch[1010101];
int am[1010101], scn;
 
bool isok(int N, string &S, int K){
	scn=0;
	for(int i=0; i<N; i++){
		if(S[i]=='H') ch[scn]='H', am[scn++]=0;
		if(S[i]=='C'){
			while(1){
				if(!scn || ch[scn-1]=='C') return 0;
				scn--;
				if(ch[scn]=='H') break;
				if(ch[scn]=='X' && am[scn]) return 0;
			}
			if(scn && ch[scn-1]=='X') am[scn-1]+=K;
			else ch[scn]='X', am[scn++]=K;
		}
		if(S[i]=='!'){
			if(!scn || ch[scn-1]!='X') return 0;
			am[scn-1]--;
			if(am[scn-1]<0) am[scn-1]=0;
		}
	}
	while(scn){
		scn--;
		if(ch[scn]=='H' || ch[scn]=='C') return 0;
		if(ch[scn]=='X' && am[scn]) return 0;
	}
	return 1;
}
 
int HicCup(string S) {
	int N=S.size();
	int mi=0, mx=N, md, dap=-1;
	while(mi<=mx){
		md=(mi+mx)/2;
		if(isok(N, S, md)) dap=md, mi=md+1;
		else mx=md-1;
	}
	return dap;
}

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