Submission #149172

#	Time	Username	Problem	Language	Result	Execution time	Memory
149172		Torat (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	33 ms	9216 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,lsa=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='H'){lsa=0; 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--;
			lsa=1;
		}
		else
		{
			if(lsa==0) 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;*/
	if(!can(0)) return -1;
	if(s==string(n,'!')) return -1;
	int mn=n,cura=0,curb=0;
	for(int i=n-1;i>=0;i--)
	{
		cura+=s[i]=='!';
		curb+=s[i]=='H';
		if(s[i]=='H') mn=min(mn,cura/curb);
	}
	return mn;
	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;
	}
	while(can(ans+1)) ans++;
	while(ans>=0 &&(!can(ans))) ans--;
	return ans;
}

Compilation message (stderr)

hiccup.cpp: In function 'int can(int)':
hiccup.cpp:14:17: warning: variable 'en' set but not used [-Wunused-but-set-variable]
  int cur=0,co=0,en=0,lsa=0;
                 ^~

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