oj.uz

Submission #149584

# Submission time Handle Problem Language Result Execution time Memory
149584 2019-09-01T06:47:09 Z 잉여로운 고3(#3749, imyujin, sebinkim) HicCup (FXCUP4_hiccup) C++17
0 / 100
 1000 ms 8312 KB 
#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;

string S;
int H[1000010];

bool f(int s, int e, int k, int x) {
	if(s > e) return true;
	int lc = s - 1;
	for(int i = s; i <= e; i++) if(S[i] == 'C') lc = i;
	if(lc == s - 1) return -1;
	for(int i = lc + 1; i <= e; i++) if(S[i] == '!') k++;
	if(k < x) return false;
	return f(s, H[lc] - 1, k - x, x) && f(H[lc] + 1, lc - 1, 0, x);
}

int HicCup(string SS) {
	S = SS;
	int N = S.size();
	int sum = 0;
	for(int i = 0; i < S.size(); i++) {
		if(S[i] == 'H') sum++;
		else if(S[i] == 'C') sum--;
		if(sum < 0) return -1;
	}
	if(sum != 0) return -1;
	int fc = S.size();
	for(int i = S.size() - 1; i >= 0; i--) if(S[i] == 'C') fc = i;
	if(fc == S.size()) return -1;
	for(int i = 0; i < fc; i++) if(S[i] == '!') return -1;

	stack<int> st;
	for(int i = 0; i < S.size(); i++) {
		if(S[i] == 'H') st.push(i);
		else if(S[i] == 'C') {
			H[i] = st.top();
			st.pop();
		}
	}

	int s = -1, e = S.size() - 1;
	while(s < e) {
		int m = (s + e + 1) / 2;
		int cnt = 0;
		if(f(0, S.size() - 1, 0, m)) s = m;
		else e = m - 1;
	}
	return s;
}

Compilation message

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++) {
                 ~~^~~~~~~~~~
hiccup.cpp:30:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(fc == S.size()) return -1;
     ~~~^~~~~~~~~~~
hiccup.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++) {
                 ~~^~~~~~~~~~
hiccup.cpp:45:7: warning: unused variable 'cnt' [-Wunused-variable]
   int cnt = 0;
       ^~~
hiccup.cpp:20:6: warning: unused variable 'N' [-Wunused-variable]
  int N = S.size();
      ^

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 14 ms 640 KB Output is correct
5 Execution timed out 1100 ms 8312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 14 ms 640 KB Output is correct
5 Execution timed out 1100 ms 8312 KB Time limit exceeded
6 Halted 0 ms 0 KB -