Submission #150714

#	Time	Username	Problem	Language	Result	Execution time	Memory
150714		usa1+samsung2 (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	32 ms	5492 KiB

hiccup

#include "hiccup.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool pred(const vector<int>& v, const int& g) {
    int rem = 0;
    for(int i=0; i<(int)v.size(); i++){
        if(v[i] >= g) {
            rem += v[i]-g;
        } else if ((v[i]+rem) >= g) {
            rem += v[i]+rem-g;
        } else return false;
    }
    return true;
}

int HicCup(std::string S) {
	int N = S.size();
        int x = 0;
        int lo = 0;
        int hi = 0;
        int ans = 0;
        vector<int> v;
        if (N==0) return 0;
        if (S[0] != 'H') return -1;

        {
            int cur = 0;
            char ex = S[0];
            for(int i = 1 ; i < N;i++) {
                const char &s = S[i];
                if((s != 'H') && (s!='C') && (s!='!')){
                    return -1;
                }
                switch(ex) {
                    case 'H':
                        if(s=='H') {
                            cur++;
                        } else if(s=='!') {
                            return -1;
                        }
                        break;
                    case 'C':
                        if(s=='C') cur--;
                        break;
                    case '!':
                        break;
                    default:
                        return -1;
                        break;
                }
                if(cur<0) return -1;
                if(s!='!')ex = s;
            }
            if(ex=='H' || cur != 0) return -1;
        }
        for(int i=N-1;i>=0;i--) {
            if(S[i] == '!') x++;
            else if(S[i] == 'C') {
                v.push_back(x);
                hi = max(hi, x);
                x=0;
            }
        }
        {
            int mid;
            while(lo<=hi){
                mid = (lo+hi)/2;
                if(pred(v, mid)) {
                    ans = max(ans, mid);
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return ans;
}

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