Submission #150208

#	Time	Username	Problem	Language	Result	Execution time	Memory
150208		Avengers (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	87 ms	38776 KiB

hiccup

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;

#include "hiccup.h"
vector<int> nums[1000006];
vector<int> v;
bool ok(int x, int id){
        v = nums[id];
        int p2 = v.size() - 1;
        int p1 = 0;
        int N = v.size();
        while(p1 <= p2){
                while(p1 < N && v[p1] >= x) p1 ++;
                while(p2 >= 0 && v[p2] == x) p2 --;
                if(p1 > p2) break;
                if(p1 == p2) return false;
                if(v[p2] < x) return false;
                if(v[p2] - x >= x - v[p1]){
                        v[p2] -= (x - v[p1]);
                        v[p1] = x;

                }
                else{
                        p2 --;
                }
        }

        return true;
}
int HicCup(std::string s) {
	int n = s.size();
	int cnt[n];
	int c =  0;
	for(int i = n - 1; i >= 0; i --){
                if(s[i] == '!') c ++;
                cnt[i] = c;
                if(s[i] == 'C') c = 0;
                else if(s[i] == 'H' && c > 0) return -1;
	}

	if(c > 0) return -1;
	stack <int> S;
	S.push(0);
	int ANS = n;
	fr(i, 0, n){
                if(s[i] == 'H') S.push(i + 1);
                else if(s[i] == 'C'){
                        if((int)(S.size()) == 1) return -1;
                        int id = S.top();
                        S.pop();
                        nums[(int)S.top()].pb(cnt[i]);
                        if(nums[id].empty()) continue;
                        int k = 0;
                        for(int b = ANS / 2; b >= 1; b /= 2){
                                while(k + b <= ANS && ok(k + b, id)) k += b;
                        }
                        ANS = min(ANS, k);


                 }
	}
        if((int)S.size() > 1)return -1;
        if(!nums[0].empty()){
                int k = 0;
                for(int b = ANS / 2; b >= 1; b /= 2){
                        while(k + b <= ANS && ok(k + b, 0)) k += b;
                }
                ANS = min(ANS, k);
        }
        return ANS;
}/*
int main(){
        cout << HicCup("HC!!HC!!!!!HC!!");
}
*/

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