Submission #150095

#	Time	Username	Problem	Language	Result	Execution time	Memory
150095		Little Piplup (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	381 ms	11428 KiB

hiccup

#include "hiccup.h"
#include<bits/stdc++.h>
//using namespace std;

int HicCup(std::string S) {
	int N = S.size();
	if ( S[0] != 'H' ) return -1;

	std::vector<int> parse;
	int temp = 0;
	for ( int i = 0 ; i < N ; ++i ) {
		if ( S[i] == 'H' ) {
			if ( temp ) {
				parse.push_back(temp);
				temp = 0;
			}
			parse.push_back(-2);
		} else if ( S[i] == 'C' ) {
			if ( temp ) {
				parse.push_back(temp);
				temp = 0;
			}
			parse.push_back(-1);
		} else {
			++temp;
		}
	}
	if ( temp ) {
		parse.push_back(temp);
	}

	int size = parse.size();

	int up = N+3, down = 0;
	while( down + 1 < up ) {
		int cur = (up + down)/2;
		//std::cout<<up<<" "<<down<<std::endl;

		std::stack<int> boo;

		for ( int i = 0 ; i < size ; ++i ) {
			//push current
			boo.push(parse[i]);

			//pop if possible
			while( boo.size() > 2 ){
				int c = boo.top();
				boo.pop();
				int b = boo.top();
				boo.pop();
				int a = boo.top();
				boo.pop();
				
				if ( a == -2 && b == -1 && c >= cur ) {

					if ( boo.empty() || boo.top() == -2 || c == cur) {
						//do nothing
					} else {		//push back
						c -= cur;
						if ( boo.top() == -1 ) {
							boo.push(c);
						} else {
							int temp = boo.top();
							boo.pop();
							boo.push(temp+c);
						}
					}

				} else {
					boo.push(a);
					boo.push(b);
					boo.push(c);
					break;
				}
			}
		}

		if ( boo.empty() ) {
			down = cur;
		} else {
			up = cur;
		}


	}

	if ( down ) {
		return down;
	} else {
		bool done = true;
		int soo = 0;
		for ( int i = 0 ; i < N ; ++i ) {
			if ( S[i] == 'H' ) ++soo;
			if ( S[i] == 'C' ) --soo;
			if ( soo < 0 ) done = false;
		}
		if ( soo ) done = false;

		if ( done ) return 0;
		else return -1;
	}
}

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