Submission #148627

#	Time	Username	Problem	Language	Result	Execution time	Memory
148627		Ian and 2-bit memory (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	161 ms	63224 KiB

hiccup

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

vector<int> level[1000055];
stack<int> sta;
vector<int> have[1000055];
int pt[1000055];
bool diu[1000055];

list<int> l;

int res;

bool trial(int x, string &S) {
	int n = S.size();

	for (int i = 0; i <= n; i++) pt[i] = 0, diu[i] = true;

	while (!sta.empty()) sta.pop();

	sta.push(n);

	for (int i = 0; i < n; i++) {
		if (S[i] == 'H') {
			sta.push(i);
		} else if (S[i] == 'C') {
			sta.pop();

			if (pt[sta.top()] < have[sta.top()].size() && have[sta.top()][pt[sta.top()]] < i && diu[sta.top()]) {
				return false;
			}

			diu[sta.top()] = false;

			while (pt[sta.top()] < have[sta.top()].size() && have[sta.top()][pt[sta.top()]] < i) {
				pt[sta.top()]++;
			}

			pt[sta.top()] += x;

			if (pt[sta.top()] > have[sta.top()].size()) {
				return false;
			}
		}
	}

	return true;
}
int HicCup(std::string S) {
	int n = S.size();

	for (int i = 0; i <= n; i++) level[i].clear();
	for (int i = 0; i <= n; i++) {
		have[i].clear();
	}

	while (!sta.empty()) sta.pop();

	sta.push(n);

	for (int i = 0; i < n; i++) {
		if (S[i] == 'H') {
			sta.push(i);
		} else if (S[i] == 'C') {
			if (sta.size() == 1) return -1;
			sta.pop();
			level[sta.top()].push_back(i);
		} else {
			have[sta.top()].push_back(i);
		}
	}

	if (sta.size() != 1) return -1;

	int lb = -1, ub = n + 1;

	while (ub - lb > 1) {
		int mid = (ub + lb) >> 1;

		if (trial(mid, S)) lb = mid;
		else ub = mid;
	}

	return lb;
}

Compilation message (stderr)

hiccup.cpp: In function 'bool trial(int, std::__cxx11::string&)':
hiccup.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pt[sta.top()] < have[sta.top()].size() && have[sta.top()][pt[sta.top()]] < i && diu[sta.top()]) {
        ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hiccup.cpp:36:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (pt[sta.top()] < have[sta.top()].size() && have[sta.top()][pt[sta.top()]] < i) {
           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hiccup.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (pt[sta.top()] > have[sta.top()].size()) {
        ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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