Submission #149158

#	Time	Username	Problem	Language	Result	Execution time	Memory
149158		mit한의대지망생 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	90 ms	16224 KiB

hiccup

#include "hiccup.h"
#include <algorithm>
#include <vector>
#include <tuple>

using namespace std;
typedef pair<int, int> pii;

int n;
char S[1000001];
int nxt[1000002];
int prv[1000002];
vector<pii> P;

bool check(int x) {
    for (int i = 1; i <= n; ++i) {
        nxt[i] = i + 1;
        prv[i] = i - 1;
    }
    for (pii _i : P) {
        int a, b;
        tie(a, b) = _i;
        int cnt = 0, i;
        for (i = nxt[b]; cnt < x && i <= n && S[i] == '!'; i = nxt[i], ++cnt);
        if (cnt < x) return 0;
        if (nxt[a] == b) {
            nxt[prv[a]] = i;
            prv[i] = prv[a];
        }
        else {
            nxt[prv[a]] = nxt[a];
            prv[nxt[a]] = prv[a];
            nxt[prv[b]] = i;
            prv[i] = prv[b];
        }
    }
    return 1;
}

int HicCup(string _S) {
    n = _S.length();
    vector<int> st;
    S[0] = 'H';
    for (int i = 0; i < n; ++i) {
        S[i + 1] = _S[i];
        if (S[i + 1] == 'H') st.push_back(i + 1);
        else if (S[i + 1] == 'C') {
            if (st.empty()) return -1;
            P.emplace_back(st.back(), i + 1);
            st.pop_back();
        }
        if (S[i] == 'H' && S[i + 1] == '!') return -1;
    }
    if (!st.empty()) return -1;
    if (P.empty()) return -1;
    int s = 0, e = n;
    sort(P.begin(), P.end(), [&](pii a, pii b) {
        return a.first > b.first;
    });
    while (s < e) {
        int m = (s + e + 1) / 2;
        if (check(m)) s = m;
        else e = m - 1;
    }
    return s;
}

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