Submission #759915

#	Time	Username	Problem	Language	Result	Execution time	Memory
759915		denniskim	HicCup (FXCUP4_hiccup)	C++17	100 / 100	54 ms	5264 KiB

hiccup

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

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll l, r;
ll Len;
string s;

int HicCup(std::string S)
{
	s = S;
	Len = (ll)s.size();
	
	l = 0, r = Len;
	
	for(ll i = 1 ; i < Len ; i++)
	{
		if(s[i] == '!' && s[i - 1] == 'H')
			return -1;
	}
	
	while(l <= r)
	{
		ll mid = (l + r) >> 1;
		stack<ll> stk;
		ll ff = 0;
		ll HC = 0;
		
		for(ll i = 0 ; i < Len ; i++)
		{
			if(s[i] == 'H')
				stk.push(1);
			
			else if(s[i] == 'C')
			{
				while(!stk.empty() && stk.top() != 1)
				{
					if(stk.top() < 0)
						ff = 1;
					
					stk.pop();
				}
				
				if(ff)
					break;
				
				if(stk.empty())
				{
					ff = 1;
					break;
				}
				
				stk.pop();
				
				if(mid)
					stk.push(-mid);
				
				HC = 1;
			}
			
			else if(s[i] == '!')
			{
				if(stk.empty())
				{
					if(!HC)
					{
						ff = 1;
						break;
					}
					
					continue;
				}
				
				if(stk.top() >= 0)
					continue;
				
				ll gap = stk.top() + 1;
				stk.pop();
				
				if(gap < 0)
					stk.push(gap);
			}
		}
		
		if(!stk.empty())
			ff = 1;
		
		if(ff)
			r = mid - 1;
		else
			l = mid + 1;
	}
	
	return (int)r;
}

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