제출 #148686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148686		ummm (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	48 ms	5028 KiB

hiccup

#include "hiccup.h"
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 10;

bool test(string s, int mid);

int HicCup(std::string s) {
	int n = s.length();
	int lo = 0, hi = n;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		// vector<int> suff(n + 2, 0);
		// vector<int> pos(n + 2), del(n + 2, 0);
		// for (int i = 0; i <= n; ++i) {
		// 	pos[i] = i + 1;
		// }
		// pos[n + 1] = n + 1;
		// for (int i = n; i >= 1; --i) {
		// 	if (s[i] == '!') {
		// 		suff[i] = 1 + suff[pos[i]];
		// 	} else if (s[i] == 'H') {
		// 		int p1 = pos[i];
		// 		while (p1 <= n and del[p1] == true) {
		// 			p1 = pos[p1];
		// 		}
		// 		int p2 = pos[p1];
		// 		if (s[p1] == 'C' and suff[p2] >= mid) {
		// 			int nxt = p2;
		// 			for (int j = 0; j < mid + 1; ++j) {
		// 				nxt = pos[p2];
		// 			}
		// 			while (nxt <= n and s[nxt] == '!' and !del[nxt]) {
		// 				del[nxt] = true;
		// 				nxt = pos[nxt];
		// 			}
		// 			pos[i - 1] = nxt;
		// 		}
		// 	}
		// }
		// bool ok = true;
		// for (int i = 0; i <= n; i = pos[i]) {
		// 	if (s[i] != '!') {
		// 		ok = false;
		// 		break;
		// 	}
		// }

		if (test(s, mid)) {
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return lo - 1;
}

bool test(string s, int mid) {
	int n = s.length();
	stack<char> stk;
	stk.push('#');
	bool first = true;
	for (int i = n - 1; i >= 0; --i) {
		if (s[i] == 'H') {
			while (!first and stk.top() == '!') {
				stk.pop();
			}
			first = false;
			if (stk.top() != 'C') {
				return false;
			}
			stk.pop();
			for (int j = 0; j < mid; ++j) {
				if (stk.top() != '!') {
					return false;
				}
				stk.pop();
			}
		} else {
			stk.push(s[i]);
		}
	}
	while (!first and stk.top() == '!') {
		stk.pop();
	}
	return stk.top() == '#';
}

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