oj.uz

Submission #151588

# Submission time Handle Problem Language Result Execution time Memory
151588 2019-09-03T15:28:57 Z leduykhongngu HicCup (FXCUP4_hiccup) C++17
0 / 100
 3 ms 508 KB 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

string S = "";
int n;
int pre[1000005], sum[1000005];
vector<int> End;
bool Check(int lim)
{
    int last = S.length() - 1;
    int cnt = 0;
    for (int R : End) {
        cnt += sum[last] - sum[R - 1];
        if (cnt < lim) return false;
        cnt -= lim;
        last = R;
    }
    return true;
}

int HicCup(std::string tmp)
{
    S = tmp;
    stack<int> st;
    for (int i = 0; i < tmp.length(); ++i) {
        sum[i] = sum[i-1];
        if (S[i] == '!') {
            if (i > 0 && S[i-1] == 'H') return false; 
            ++sum[i];
            continue;
        }
        if (S[i] == 'H') {
            st.push(i);
        }
        else {
            assert(S[i] == 'C');
            int L = st.top();
            pre[i] = L;
            st.pop();
            End.push_back(i);
        }
    }
    if (st.size()) return -1;
    reverse(End.begin(), End.end());
    int lef = 0, rig = S.length(), ans = -1;
    while (lef <= rig)
    {
        int mid = (lef + rig)/2;
        if (Check(mid))
        {
            ans = max(ans, mid);
            lef = mid + 1;
        }
        else rig = mid - 1;
    }
    return ans;
}

Compilation message

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < tmp.length(); ++i) {
                     ~~^~~~~~~~~~~~~~

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -