Submission #148631

#	Time	Username	Problem	Language	Result	Execution time	Memory
148631		还没编好 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	38 ms	8320 KiB

hiccup

#include "hiccup.h"
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 3333333
int st[SZ],sn,ma[SZ],aa=2e9,N;
string s;
void go(int l,int r)
{
	if(l>r) return;
	int w=0,su=0,c=0;
//	cout<<l<<"~"<<r<<":";
//	for(int j=l;j<=r;++j) cout<<s[j];
//	cout<<"\n";
	for(int g=r;g>=l;--g)
	{
		if(s[g]=='!')
		{
			++w;
			continue;
		}
		if(s[g]=='C')
		{
			su+=w,++c,
			aa=min(aa,su/c),w=0;
			go(ma[g]+1,g-1);
			g=ma[g];
		}
		else throw "GG";
	}
	if(w) aa=-1;
}
int HicCup(std::string S) {
	N = S.size(); s=S;
	for(int i=0;i<N;++i)
	{
		if(S[i]=='!') continue;
		if(S[i]=='H') st[++sn]=i;
		else
		{
			if(!sn) return -1;
			int g=st[sn--];
			ma[g]=i; ma[i]=g;
		}
	}
	if(sn) return -1;
	go(0,N-1);
	return aa;
}
#ifdef LOCAL
#define st my_sty
#include "grader.cpp"
#endif

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