Submission #593067

#	Time	Username	Problem	Language	Result	Execution time	Memory
593067		GioChkhaidze	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	41 ms	3424 KiB

monochrome

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

string s;
ll n, ans;
vector < int > B, W;

ll check(int x) {
	ll res = 0;
	for (int i = 0; i < W.size(); ++i) {
		int l = W[i];
		int r = B[(i + x) % n];
		int len = abs(r - l) - 1;
		len = min(len, 2 * (int)n - len - 2);
		res += len;
	}
	res /= 2;
	ans = max(res, ans);
	return res;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> s;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == 'B')
			B.pb(i);
				else 
			W.pb(i);
	}
	
	int l = 0, r = n - 1, mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (check(mid) < check(mid + 1)) {
			l = mid + 1;
		}
			else {
			r = mid - 1;		
		}
	}
	cout << ans << "\n";
}

Compilation message (stderr)

monochrome.cpp: In function 'long long int check(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 < W.size(); ++i) {
      |                  ~~^~~~~~~~~~
monochrome.cpp: At global scope:
monochrome.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main () {
      | ^~~~
monochrome.cpp: In function 'int main()':
monochrome.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~

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