Submission #300516

#	Time	Username	Problem	Language	Result	Execution time	Memory
300516		mode149256	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	854 ms	9100 KiB

monochrome

/*input
16
WWWBWBBBBWWBWWBWWBBWWBBBWBBBWWBW
*/
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second

using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using str = string;

int N;
vi sk;
vi num;
vi R, B;

// k = [0; N/2)
ll kiek(int k) { // black i match with white i + k
	int cnt = 0;
	vi in(N, 0);

	vi other(N, -1);

	ll ret = 0;

	auto prN2 = [&](int a, int x) {
		return (a + x + (N / 2)) % (N / 2);
	};
	auto prN = [&](int a, int x) {
		return (a + x + N) % N;
	};

	for (int i = 0; i < N / 2; ++i)
	{
		// printf("i = %d, r = %d, B = %d\n", i, R[i], )
		other[R[i]] = B[prN2(i, k)];
		other[B[prN2(i, k)]] = R[i];
	}

	auto inv = [&](int a) {
		cnt -= (in[other[a]] ^ in[a]);
		in[a] ^= 1;
		cnt += (in[other[a]] ^ in[a]);
	};

	for (int i = R[0] + 1; i != B[k]; i = prN(i, 1))
	{
		inv(i);
	}

	// for (int i = 0; i < N; ++i) printf("%d %d\n", i+1, other[i]+1);
	int r = R[0];
	int b = B[k];
	for (int i = 0; i < N / 2; ++i)
	{
		while (r != R[i]) {
			r = prN(r, 1);
			// printf("r = %d\n", r);
			inv(r);
		}
		while (b != B[prN2(i, k)]) {
			// printf("b = %d\n", b);
			inv(b);
			b = prN(b, 1);
		}
		// printf("i = %d, R = %d, B = %d, cnt = %d\n", i, R[i], B[prN2(i, k)], cnt);
		ret += cnt;
		// inv(r);
		// 	printf("r = %d\n", r);
		// inv(b);
		// 	printf("b = %d\n", b);
	}
	return ret / 2;
}

int main() {
	cin >> N;
	N <<= 1;
	sk.resize(N);
	num.resize(N);
	{
		str s;
		cin >> s;
		for (int i = 0; i < N; ++i)
		{
			if (s[i] == 'W') {
				num[i] = (int)B.size();
				B.emplace_back(i);
			}
			else {
				num[i] = (int)R.size();
				R.emplace_back(i);
			}
			sk[i] = (s[i] == 'W');
		}
	}

	int l = 0;
	int h = N / 2 - 1;
	int m1, m2;

	while (h - l > 4) {
		int d = (h - l) / 3;
		m1 = l + d;
		m2 = h - d;

		if (kiek(m1) <= kiek(m2)) {
			l = m1;
		} else {
			h = m2 - 1;
		}
	}

	ll ats = 0;
	for (int i = l; i <= h; ++i)
	{
		ats = max(ats, kiek(i));
	}

	printf("%lld\n", ats);
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65