Submission #148877

#	Time	Username	Problem	Language	Result	Execution time	Memory
148877		shdut0901 (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	44 ms	15104 KiB

hiccup

#include "hiccup.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <assert.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b - 1; i >= a; i--)
#define ll long long
#define x first
#define y second
#define vi vector<int>
#define pii pair<int, int>
#define SZ(x) (int)(x.size())
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define inf 1000000007
#define DBG(x) cerr << (#x) << "=" << x << "\n";

#define N 100005

template<typename U, typename V> void Min(U &a, const V &b){if(a > b) a = b;}
template<typename U, typename V> void Max(U &a, const V &b){if(a < b) a = b;}
template<typename U, typename V> void add(U &a, const V &b){a = (a+b) % mod;}

int get(char c){
	if(c == 'H')return 0;
	else if(c == 'C')return 1;
	else return 2;
}
int HicCup(std::string s) {
	int n = s.size();
	vi from(n), vis(n, 0), q(n);
	int a[3] = {0};
	rep(i, 0, n){
		a[get(s[i])]++;
	}
	if(a[0] != a[1] || a[0] == 0)return -1;
	int m = 0, k, flag = 0;
	rep(i, 0, n){
		k = get(s[i]);
		if(k == 0)q[m++] = i, flag = 1;
		else if(k == 1){
			if(m == 0)return -1;
			from[i] = q[--m];
			if(flag){
				if(from[i] != i-1)return -1;
			}
			flag = 0;
		}
	}
	if(m)return -1;
	int r = a[2] / a[0];
	int l = 0, now = 0;
	while(l <= r){
		m = (l + r) >> 1;
		int rem = 0, ok = 1;
		now++;
		per(i, 0, n)if(vis[i] != now){
			k = get(s[i]);
			if(k == 2)rem++;
			else if(k == 1){
				if(rem < m){ok = 0;break;}
				k = from[i];
				vis[k] = now;
				rem -= m;
			}
		}
		if(ok)l = m + 1;
		else r = m - 1;
	}
	l--;
	return l;
}

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