Submission #149697

#	Time	Username	Problem	Language	Result	Execution time	Memory
149697		Welcome to osu! (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	65 ms	9344 KiB

hiccup

#include <bits/stdc++.h>
#include "hiccup.h"
using namespace std;
const int MN = 1e6+5;
int H[MN],C[MN],L[MN];
int numH,numC=-1;
stack<int> st;

int proc(int s, int e, int d)
{
    int res = MN, cnt, num;
    if(e-s+d==0){
        if(H[s]+1!=C[e]) return -1;
        else return MN;
    }
    if(H[s+1]!=H[s]+1) return -1;
    int s0 = s+1, e0 = L[s0];
    priority_queue<int, vector<int>, greater<int> > PQ;
    while(s0<=e+d){
        res = min(res,proc(s0,e0,d+1));
        if(e0+2>e){
            cnt = C[e]-C[e0]-1;
            //if(s==0) cout << cnt << '\n';
            break;
        }
        //if(s==0) cout << H[e0+d+2]-C[e0]-1 << '\n';
        PQ.push(H[e0+d+2]-C[e0]-1);
        s0 = e0+d+2, e0 = L[s0];
    }
    PQ.push(0);
    while(cnt){
        num = PQ.top();
        PQ.pop();
        PQ.push(num+1);
        cnt--;
    }
    res = min(res,PQ.top());
    //cout << s << ' ' << e << ' ' << d << ' ' << res << '\n';
    return res;
}

int HicCup(std::string S) {
	int N = S.size();
	for(int i=0; i<N; i++){
       if(S[i]=='!') continue;
       if(S[i]=='H'){
            numH++;
            st.push(numH);
            H[numH] = i;
        }
        if(S[i]=='C'){
            numC++;
            if(numH<numC+1) return -1;
            C[numC] = i;
            L[st.top()] = numC;
            st.pop();
        }
	}
	if(numH!=numC+1) return -1;
    H[0] = -1;
    L[0] = numH;
    C[numH] = N;
    return proc(0,numH,0);
}

Compilation message (stderr)

hiccup.cpp: In function 'int proc(int, int, int)':
hiccup.cpp:35:12: warning: 'cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
         cnt--;
         ~~~^~

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