oj.uz

Submission #151569

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

string S = "";
int n;

bool Check(int lim)
{
    int cntCur = 0;
    stack<int> cnt;
    stack<char> st;
    #define vedify(x) if ((x) == 0) return false;
    char pre = '#';
    for (char x : S) {
        if (x != '!') {
            if (cntCur >= lim) {
                while (cntCur >= lim) {
                    vedify(st.size() >= 2);
                    vedify(st.top() == 'C');
                    st.pop();
                    vedify(st.top() == 'H');
                    st.pop();
                    cntCur -= lim;
                    if (cntCur > 0) {
                        if (st.size() == 0) cntCur = 0;
                        else if (st.top() == 'C') {
                            assert(cnt.size() >= 0);
                            cntCur += cnt.top();
                            cnt.pop();
                        }
                        else if (st.top() == 'H') {
                            cntCur = 0;
                        }
                    }
                }
                cnt.push(cntCur);
                // cerr << cntCur << endl;
                // if (x == '#') {
                //     cerr << "lim = "  << lim << endl;
                //     cerr << st.size() << ' ';
                //     while (st.size()) {
                //         cerr << st.top() << ' ';
                //         st.pop();
                //     }
                // }
                if (x == '#' && st.size() == 0) return true;
                if (x == '#') return false;
            }
            else { //cntCur < lim
                if (pre == '!')
                    cnt.push(cntCur);
                cntCur = 0;
            }
            if (x == 'H')
                st.push(x);
            else { //x == 'C'
                vedify(st.size() >= 1 && st.top() == 'H');
                st.push(x);
            }
        }
        else { //x == '!'
            vedify(st.size() >= 2 && st.top() == 'C');
            ++cntCur;
        }
        pre = x;
    }
    assert(-1);
    return true;
}

int HicCup(std::string tmp)
{
    for (int i = 0; i < tmp.length(); ++i)
    {
        S.push_back(tmp[i]);
        if (tmp[i] == 'C') S.push_back('!');
    }
    n = S.length();
    S.push_back('#');
//    cout << Check(1);
//    for (int i = 1; i <= 1; ++i)
//        cout << Check(i) << endl;
    int lef = 0, rig = n, ans = -1;
    while (lef <= rig)
    {
        int mid = (lef + rig)/2;
        if (Check(mid))
        {
            ans = max(ans, mid);
            lef = mid + 1;
        }
        else rig = mid - 1;
    }
    if (ans != -1) --ans;
    return ans;
}

Compilation message

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:77: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 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 3 ms 504 KB Output isn't correct
5 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 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 3 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -