oj.uz

Submission #293116

# Submission time Handle Problem Language Result Execution time Memory
293116 2020-09-07T16:32:32 Z Berted Power Plant (JOI20_power) C++14
0 / 100
 0 ms 256 KB 
#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

power.cpp: In function 'long long int solve(int)':
power.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++)
      |                  ~~^~~~~~~~~~~~~
power.cpp: In function 'long long int binser(int, int)':
power.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int M = L + R >> 1;
      |           ~~^~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -