제출 #149216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149216		욱방켜!! (twitch.tv/wookje) (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	935 ms	19428 KiB

hiccup

#include "hiccup.h"
#include <stack>
#include <vector>
#include <iostream>
using namespace std;

bool try_to_pop(stack<pair<int,int>> &st, int X){
	// we want H_a C_b where a<=0 and b>=X
	if(st.size() < 2) return false;
	auto [b1, b2] = st.top(); st.pop();
	auto [a1, a2] = st.top(); st.pop();
	if(a1 != 1 || b1 != 2 || a2 > 0 || abs(b2) < X){
		st.push({a1,a2}); st.push({b1,b2});
		return false;
	}

	// combine ??(-a2) with !!(b2-X)
	int newex = -a2 + abs(b2)-X;
	if(st.empty()) st.push({0, -newex});
	else if(st.top().second > 0) st.top().second+= newex;
	else st.top().second-= newex;
	return true;
}

bool possible(vector<pair<int,int>> &V, int X){
	stack<pair<int,int>> st;
	for(auto [ct, ex]: V){
		st.push({ct,ex});
		while(try_to_pop(st, X));
	}
	if(st.empty()) return true;
	if(st.size() > 1) return false;
	return st.top().first == 0 && st.top().second <= 0;
}

int HicCup(std::string S) {
	int N = S.size();
	vector<pair<int,int>> V;
	// first: type. blank 0, H 1, C 2
	// second: !

	for(char c: S){
		if(c == '!'){
			if(V.empty()) V.push_back({0, 1});
			else V.back().second++;
		}
		else if(c == 'H') V.push_back({1, 0});
		else V.push_back({2, 0});
	}

	//for(auto [a,b]: V) cout<<a<<' '<<b<<endl;

	int lo = 0, hi = 1000000, ans = -1;
	while(lo <= hi){
		int mid = (lo+hi)/2;
		//cout<<"TRYING "<<mid<<endl;
		if(possible(V, mid)) ans = mid, lo = mid+1;
		else hi = mid-1;
	}
	if(ans > -1) return ans;
	return -1;
}

컴파일 시 표준 에러 (stderr) 메시지

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:37:6: warning: unused variable 'N' [-Wunused-variable]
  int N = S.size();
      ^

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