Submission #742873

#	Time	Username	Problem	Language	Result	Execution time	Memory
742873		flappybird	Toilets (JOI16_toilets)	C++17	36 / 100	230 ms	8136 KiB

toilets

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
string str[MAX];
ll K[MAX];
int fs[MAX];
int ms[MAX];
struct node {
	ll sum = 0;
	ll lmx = 0;
	node(int x = 0) { sum = lmx = x; }
};
node operator+(node n1, node n2) {
	node ret;
	ret.sum = n1.sum + n2.sum;
	ret.lmx = max(n1.lmx, n1.sum + n2.lmx);
	return ret;
}
node operator*(node n1, ll x) {
	if (!x) return node();
	node res = n1 * (x / 2);
	res = res + res;
	if (x & 1) res = n1 + res;
	return res;
}
node gets(int s, int n = -1) {
	if (!~n) n = str[s].size();
	int i;
	node ret;
	for (i = 0; i < n; i++) {
		if (str[s][i] == 'M') ret = ret + node(-1);
		else ret = ret + node(1);
	}
	return ret;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N;
	int M;
	cin >> N >> M;
	int i, j;
	ll allf = 0;
	for (i = 1; i <= M; i++) {
		cin >> str[i] >> K[i];
		for (auto v : str[i]) if (v == 'F') fs[i]++;
		ms[i] = str[i].size() - fs[i];
		allf += 1ll * fs[i] * K[i];
	}
	if (allf < N) {
		cout << -1 << ln;
		return 0;
	}
	ll lim = (allf - N) * 2 + 1;
	ll l, r;
	l = -1;
	r = N * 2 - allf;
	while (r - l > 1) {
		ll m = l + r >> 1;
		ll rem = m;
		node res = node();
		int isend = 0;
		for (i = M; i >= 1; i--) {
			if (isend) {
				res = (gets(i) * K[i]) + res;
				continue;
			}
			if (rem >= 1ll * ms[i] * K[i]) {
				rem -= 1ll * ms[i] * K[i];
				res = res + node(fs[i] * K[i]);
			}
			else {
				ll n = rem / ms[i];
				rem -= 1ll * ms[i] * n;
				res = res + node(fs[i] * n);
				int sfs = 0;
				for (j = str[i].size() - 1; j >= 0; j--) {
					if (!rem) break;
					if (str[i][j] == 'F') sfs++;
					else rem--;
				}
				res = gets(i, j) + node(sfs) + res;
				res = gets(i) * (K[i] - n - 1) + res;
				isend = 1;
			}
		}
		res = node(-m) + res;
		if (res.lmx > lim) l = m;
		else r = m;
	}
	cout << r << ln;
}

Compilation message (stderr)

toilets.cpp: In function 'int main()':
toilets.cpp:70:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |   ll m = l + r >> 1;
      |          ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 22 / 22
• Subtask 3: 0 / 64