Submission #293120

#	Time	Username	Problem	Language	Result	Execution time	Memory
293120		Berted	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	68 ms	1944 KiB

monochrome

#include <iostream>
#include <vector>
using namespace std;
int n; string s;
vector<int> C[2];
long long ans = 0;
bool matchWith[100001];

long long solve(int x)
{
	long long temp = 0;
	for (int i = 0; i < C[0].size(); i++)
	{
		temp += min(abs(C[1][(i + x) % C[1].size()] - C[0][i]), n - abs(C[1][(i + x) % C[1].size()] - C[0][i]));		
	}
	return temp;
}

long long binser(int L, int R)
{
	while (L < R)
	{
		int M = L + R >> 1;
		if (solve(M) < solve(M + 1)) {R = M;}
		else {L = M + 1;}
	}

	long long ret = 1e18;
	for (int i = max(0, L - 5); i < min(L + 5, (int)C[0].size()); i++) {ret = min(ret, solve(i));}
	return ret;
}

int main()
{
	cin >> n >> s;
	for (int i = 0; i < n; i++)
	{
		if (s[i] == s[i + n]) {C[s[i] == 'W'].push_back(i);}
	}
	ans = (long long)n * (n - 1) / 2;
	
	if (C[0].size())
	{
		long long res = 1e18;
		res = min(binser(0, (int)C[0].size() / 2 - 1), binser((int)C[0].size() / 2, (int)C[0].size() - 2));
		ans -= res;
	}

	cout << ans << "\n";
	
	return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'long long int solve(int)':
monochrome.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (int i = 0; i < C[0].size(); i++)
      |                  ~~^~~~~~~~~~~~~
monochrome.cpp: In function 'long long int binser(int, int)':
monochrome.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int M = L + R >> 1;
      |           ~~^~~

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