oj.uz

Submission #149717

# Submission time Handle Problem Language Result Execution time Memory
149717 2019-09-01T07:01:06 Z Little Piplup(#3742, gratus907, DHdroid, coffeetea99) HicCup (FXCUP4_hiccup) C++17
24 / 100
 469 ms 7504 KB 
#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;

	int up = N+3, down = 0;

	while( down + 1 < up ) {
		int cur = (up + down)/2;
		std::stack<int> boo;

		//std::cout<<up<<" "<<down<<std::endl;

		for ( int i = 0 ; i < N ; ++i ) {

			//push next
			if ( S[i] == 'H' ) {
				boo.push(-2);
			} else if ( S[i] == 'C' ) {
				boo.push(-1);
			} else {
				if ( boo.empty() || boo.top() < 0 ) {		//h or c is current
					boo.push(1);
				} else {
					int temp = boo.top();
					boo.pop();
					boo.push(temp+1);
				}
			}
			
			//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 ) {
					c -= cur;
					if ( c ) {
						if ( boo.empty() || boo.top() < 0 ) {
							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() || (boo.size() == 1 && boo.top() >= 0) ) {
			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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 18 ms 704 KB Output is correct
5 Correct 453 ms 7472 KB Output is correct
6 Correct 14 ms 3328 KB Output is correct
7 Correct 14 ms 3328 KB Output is correct
8 Correct 461 ms 7492 KB Output is correct
9 Correct 464 ms 7496 KB Output is correct
10 Correct 469 ms 7504 KB Output is correct
11 Correct 6 ms 384 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 18 ms 704 KB Output is correct
5 Correct 453 ms 7472 KB Output is correct
6 Correct 14 ms 3328 KB Output is correct
7 Correct 14 ms 3328 KB Output is correct
8 Correct 461 ms 7492 KB Output is correct
9 Correct 464 ms 7496 KB Output is correct
10 Correct 469 ms 7504 KB Output is correct
11 Correct 469 ms 7136 KB Output is correct
12 Correct 382 ms 4612 KB Output is correct
13 Correct 323 ms 3328 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Incorrect 362 ms 3456 KB Output isn't correct
16 Halted 0 ms 0 KB -