oj.uz

답안 #150691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150691 2019-09-01T08:49:28 Z GucciBelt(#3697, PeppaPig, win11905, DodgeBallMan) HicCup (FXCUP4_hiccup) C++17
0 / 100
 1000 ms 262144 KB 
#include "hiccup.h"
#define pii pair<int, int>
#define x first
#define y second
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+5;

int n, lvl[N];
stack<int> stk[N];

bool checkFunction(string str, int mid) {
	int  cnt = 0;
	stack<pii> stk;
	for(int i = 0; i < n; ++i) {
		if(str[i] == 'C') {
			cnt--;
			if(!stk.empty() and stk.top().y > cnt) return false;
			stk.emplace(0, cnt);
		}
		if(str[i] == '!') {
			if(stk.empty()) continue;
			pii now = stk.top(); stk.pop();
			if(++now.x == mid) continue;
			stk.emplace(now);
		} 
		if(str[i] == 'H') {
			cnt++;
		}
	}
	return stk.empty();
}

int HicCup(string S) {
	n = S.size();
	int cnt = 0, pv = -1;
	for(int i = 0; i < n; ++i) {
		if(S[i] == 'H') cnt++, pv = -1;
		if(S[i] == 'C') {
			lvl[i] = cnt;
			if(!~--cnt) return -1;
			else pv = i;
		}
		if(S[i] == '!') {
			if(pv == -1) return -1;	
			else lvl[i] = lvl[pv];
		}
	}
	if(cnt) return -1;
	int l = 0, r = S.size();
	while(l < r) {
		int mid = (l + r + 1) >> 1;
		if(checkFunction(S, mid)) l = mid;
		else r = mid-1;
	}	
	return l;
}

Subtask #1
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1043 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 76.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1043 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -