Submission #149222

#	Time	Username	Problem	Language	Result	Execution time	Memory
149222		shdut0901 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	48 ms	11148 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), q(n);
	int a[3] = {0};
	rep(i, 0, n){
		a[get(s[i])]++;
	}
	if(a[0] != a[1] || a[0] == 0)return -1;
	if(get(s[0]) != 0)return -1;
	int m = 0, k, last = -1, pos;
	int r = a[2] / a[0];
	int l = 0;
	rep(i, 0, n){
		k = get(s[i]);
		if(k == 0){
			q[m++] = i;
			if(last == 0 && pos != i - 1)return -1;
			last = 0, pos = i;
		}
		else if(k == 1){
			if(m == 0)return -1;
			if(last == 0 && q[m-1] != i-1)return -1;
			else if(last == 1){
				Min(r, i - pos - 1);
			}
			m--;
			last = 1, pos = i;
		}
	}
	if(m)return -1;
	while(l <= r){
		m = (l + r) >> 1;
		int rem = 0, ok = 1;
		per(i, 0, n){
			k = get(s[i]);
			if(k == 2)rem++;
			else if(k == 1){
				if(rem < m){ok = 0;break;}
				rem -= m;
			}
		}
		if(ok)l = m + 1;
		else r = m - 1;
	}
	l--;
	return l;
}

Compilation message (stderr)

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:57:17: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(last == 0 && pos != i - 1)return -1;
       ~~~~~~~~~~^~~~~~~~~~~~~~~

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