Submission #149993

#	Time	Username	Problem	Language	Result	Execution time	Memory
149993		Avengers (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	86 ms	38780 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];
bool ok(int x, int id){
        int c = 0;
        for(auto u : nums[id]){
                if(u > x){
                        if(u - x >= c) c = 0;
                        else{
                                c -= (u - x);
                        }
                }
                else{
                        c += (x - u);
                }
        }
        return c == 0;
}
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;
}

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