Submission #148870

#	Time	Username	Problem	Language	Result	Execution time	Memory
148870		Torat (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	78 ms	8192 KiB

hiccup

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

using namespace std;

const int N=1e6+6;

string s;
int n;
int nxt[N];

int can(int x)
{
	int cur=0,co=0,en=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='H') co++;
		else if(s[i]=='C')
		{
			if(co==0) return 0;
			en=1; cur=max(cur,i-1);
			for(int j=0;j<x;j++)
			{
				cur=nxt[cur];
				//cout << i << " " << cur << endl;
				if(cur>n) return 0;
			}
			co--;
		}
		else
		{
			if(!en) return 0;
		}
	}
	if(co) return 0;
	return 1;
}

int HicCup(std::string ss) {
	s=ss;
	n=s.size();
	nxt[n]=nxt[n+1]=nxt[n-1]=n+1;
	for(int i=n-2;i>=0;i--)
	{
		nxt[i]=nxt[i+1];
		if(s[i+1]=='!') nxt[i]=i+1;
	}
	/*for(int i=0;i<4;i++)
		cout << can(i) << endl;
	return 0;*/
	int st=0,en=n,ans=-1;
	while(st<=en)
	{
		int mid=(st+en)/2;
		if(can(mid)){ans=mid; st=mid+1;}
		else en=mid-1;
	}
	if(can(ans+1)) ans++;
	if(ans>=0 &&(!can(ans))) ans--;
	return ans;
}

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