Submission #148472

#	Time	Username	Problem	Language	Result	Execution time	Memory
148472		White Fairy (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	59 ms	3328 KiB

hiccup

#include "hiccup.h"

#include <bits/stdc++.h>

using namespace std;

bool can(string & S, int & it, int x) {
  int cnt = 0, need = 0;
  while (it < S.size()) {
    if (cnt > 0 && need == 0) {
      --cnt;
      need = x;
    }
    char ch = S[it++];
    if (ch == '!') {
      if (need > 0) {
        --need;
      }
    }
    else  if (ch == 'H') {
      bool res = can(S, it, x);
      if (!res)
        return false;
      ++cnt;
    }
    else {
      return cnt <= 0 && need <= 0;
    }
  }
  return cnt <= 0 && need <= 0;
}

int HicCup(std::string S) {
	int N = S.size();
  int open = 0;
  for (int i = 0; i < N; ++i) {
    if (S[i] == 'H')
      ++open;
    else if (S[i] == 'C')
      --open;
    if (open < 0)
      return -1;
  }
  if (open != 0)
    return -1;
  if (S[0] == '!')
    return -1;
  for (int i = 0; i + 1 < N; ++i) {
    if (S[i] == 'H' && S[i+1] == '!')
      return -1;
  }
  int low = 0, hi = N;
  while (low < hi) {
    int mid = (low + hi + 1) >> 1;
    int it = 0;
    if (can(S, it, mid))
      low = mid;
    else
      hi = mid-1;
  }
	return low;
}

Compilation message (stderr)

hiccup.cpp: In function 'bool can(std::__cxx11::string&, int&, int)':
hiccup.cpp:9:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (it < S.size()) {
          ~~~^~~~~~~~~~

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