Submission #149356

#	Time	Username	Problem	Language	Result	Execution time	Memory
149356		JeffreyHo (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	122 ms	11424 KiB

hiccup

#include "hiccup.h"
#include <vector>
#include <bits/stdc++.h>

int HicCup(std::string s) {
    int n = (int)s.size(), c = 0;
    bool b = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'H') c++, b = 1;
        if (s[i] == 'C') c--, b = 1;
        if (c < 0) return -1;
    }
    if (s.empty()) return 0;
    if (s[0] == '!') return -1;
    if (c) return -1;
    for (int i = 1; i < n; i++) if (s[i] == '!' && s[i - 1] == 'H') return -1;
    int l = 0, r = 1890328;
    while (l + 1 < r) {
        int m = (l + r) >> 1, c = 0;
        bool y = 0;
        std::vector<std::pair<int, int>> a = {{-1, -1890328}};
        std::vector<int> b;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'H') b.push_back(i);
            if (s[i] == 'C') c -= m, a.push_back({b.back(), 0}), b.pop_back();
            if (c < -20000328) break;
            if (s[i] == '!') {
                c++;
                a.back().second++;
                if (a.back().second == m) {
                    int b = a.back().first;
                    a.pop_back();
                    if (a.back().first > b) y = 1;
                }
            }
            if (c > 0) c = 0;
        }
        if (c || a.size() > 1 || y) r = m;
        else l = m;
    }
    return l;
}

Compilation message (stderr)

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:7:10: warning: variable 'b' set but not used [-Wunused-but-set-variable]
     bool b = 0;
          ^

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