Submission #613084

#	Time	Username	Problem	Language	Result	Execution time	Memory
613084		penguinhacker	HicCup (FXCUP4_hiccup)	C++17	100 / 100	99 ms	34856 KiB

hiccup

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

const int mxN=1e6+2;
int n=1, cnt[mxN], ans=69696969;
stack<int> stk;
vector<int> adj[mxN];

void dfs(int u=0) {
	for (int v : adj[u])
		dfs(v);
	reverse(adj[u].begin(), adj[u].end());
	int cur=0;
	for (int i=0; i<adj[u].size(); ++i) {
		cur+=cnt[adj[u][i]];
		ans=min(ans, cur/(i+1));
	}
}

int HicCup(string s) {
	stk.push(0);
	for (int i=0; i<s.size(); ++i)
		if (s[i]=='!'&&(!i||s[i-1]=='H'))
			return -1;
	for (int i=0; i<s.size(); ++i) {
		if (s[i]=='H') {
			adj[stk.top()].push_back(n);
			stk.push(n++);
		} else if (s[i]=='C') {
			if (stk.size()==1)
				return -1;
			for (; i+1<s.size()&&s[i+1]=='!'; ++i, ++cnt[stk.top()]);
			stk.pop();
		}
	}
	if (stk.size()!=1||n==1)
		return -1;
	dfs();
	return ans;
}

Compilation message (stderr)

hiccup.cpp: In function 'void dfs(int)':
hiccup.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for (int i=0; i<adj[u].size(); ++i) {
      |                ~^~~~~~~~~~~~~~
hiccup.cpp: In function 'int HicCup(std::string)':
hiccup.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i=0; i<s.size(); ++i)
      |                ~^~~~~~~~~
hiccup.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i=0; i<s.size(); ++i) {
      |                ~^~~~~~~~~
hiccup.cpp:33:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for (; i+1<s.size()&&s[i+1]=='!'; ++i, ++cnt[stk.top()]);
      |           ~~~^~~~~~~~~

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