제출 #151570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151570		leduykhongngu	HicCup (FXCUP4_hiccup)	C++17	24 / 100	59 ms	7788 KiB

hiccup

#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 = 1, 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 24 / 24
• Subtask 2: 0 / 76