Submission #1221427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221427		sleepntsheep	Toilets (JOI16_toilets)	C++20	36 / 100	975 ms	22496 KiB

toilets

#include <cstdio>
#include <set>
#include <deque>
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;

#define N 200005

int sub1() {
	int n, answer, perm[22];
	char s[22], s0[22];
	stack<int> sm,sf;
	answer = 1e9;
	scanf("%d%*d%s%*d", &n, s);

	int count_m = count(s, s + n + n, 'M');
	for (int i = 2 * n; i--; ) {
		if (s[i] == 'M') sm.push(i);
		else sf.push(i);
	}

	memcpy(s0, s, sizeof s);

	for (int m = 0; m < (1 << (n << 1)); ++m) {
		if (__builtin_popcount(m) != count_m)
			continue;
		memcpy(s, s0, sizeof s);

		for (int j = 0; j < 2 * n; ++j) {
			if ((m >> j) & 1)
				s[j] = 'M';
			else
				s[j] = 'F';
		}


		int ok = 1;
		for (int j = 0; j < 2 * n; j += 2) {
			if (s[j] == s[j + 1] and s[j] == 'M') {
				auto it = find(s + j, s + 2 * n, 'F');
				if (it == 2 * n + s) {
					ok = 0;
					break;
				}
				rotate(s + j + 1, it, it + 1);
			}
		}

		if (!ok)
			continue;

		auto sf_ = sf, sm_ = sm;

		for (int j = 0; j < 2 * n; ++j) {
			if ((m >> j) & 1)
				perm[j] = sm_.top(), sm_.pop();
			else
				perm[j] = sf_.top(), sf_.pop();
		}


		int here = 0;
		for (int i = 0; i < 2 * n; ++i) {
			int x = 0;
			for (int j = 0; j < i; ++j)
				x += perm[j] > perm[i];
			here = max(here, x);
		}
		answer = min(answer, here);
	}

	printf("%d\n", answer >= 1e9 ? -1 : answer);
	exit(0);
	return 0;
}

bool String_IsUsable(const string &s) {
	int n = s.size() >>1;

	int i_, i;

	set<pair<long long, char> > st;
	set<long long> sf;

	for (i_ = 0; i_ < 2 * n; ++i_) {
		st.insert(make_pair(i_ * 300000ll, s[i_]));
		if (s[i_] == 'F')
			sf.insert(i_ * 300000ll);
	}

	//printf(" Checking %s\n", s.c_str());
	while (st.size()) {
		auto x1 = *st.begin();
		st.erase(st.begin());
		auto x2 = *st.begin();
		st.erase(st.begin());

		if (x1.second == 'M' and x2.second == 'M') {
			while (sf.size() && *sf.begin() < x2.first)
				sf.erase(sf.begin());
			if (sf.empty())
				return false;
			//printf(" Need help \n");
			long long y = *sf.begin();
			//printf(" %lld -> %lld\n", x2.first, y);
			sf.erase(y);
			st.insert(x2);
			st.erase(make_pair(y, 'F'));
		} else {
		}
	}
	return true;
}

namespace sub2 {
	int n, _;
	string s0;

	int check(int loose) {
		string s;

		deque<pair<int, int> > wom;
		int miku = 0;

		for (int i = 0; i < 2 * n; ++i) {
			if (s0[i] == 'M') {
				s += 'M';
				++miku;
				while (wom.size() and miku == wom[0].first) {
					s += 'F';
					wom.pop_front();
				}
			} else
				wom.push_back(make_pair(miku + loose, i));
			while (wom.size() and miku == wom[0].first) {
				s += 'F';
				wom.pop_front();
			}
		}
		while (wom.size())
			s += 'F', wom.pop_back();

		//printf(" Loose = %d, built %s, usable = %d\n", loose,s.c_str(), (int)String_IsUsable(s));

		return (String_IsUsable(s));
	}

	void Main() {
		cin >> n >> _ >> s0 >> _;
		int x = n;
		for (int j = 1 << 19; j >>= 1;) {
			if (x >= j && check(x - j))
				x -= j;
		}
		if (x == n)
			cout << "-1\n";
		else
			cout << x << '\n';
	}
}

int main() {
	sub2::Main();
}

Compilation message (stderr)

toilets.cpp: In function 'int sub1()':
toilets.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%*d%s%*d", &n, s);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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