Submission #953551

#	Time	Username	Problem	Language	Result	Execution time	Memory
953551		NeroZein	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	39 ms	3044 KiB

monochrome

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> black, white; 
  for (int i = 1; i <= n * 2; ++i) {
    char c;
    cin >> c;
    if (c == 'B') {
      black.push_back(i);
    } else {
      white.push_back(i); 
    }
  }
  auto f = [&](int j) {
    long long ret = 0;
    for (int i = 0; i < n; ++i) {
      int x = white[i];
      int y = black[(j + i) % n];
      ret += min(abs(x - y), 2 * n - abs(x - y)) - 1; 
    }
    return ret; 
  }; 
  int l = 0, r = n - 1;
  while (l < r) {
    int mid = (l + r) / 2; 
    long long c1 = f(mid), c2 = f(mid + 1);
    if (c1 < c2) {
      l = mid + 1; 
    } else {
      r = mid;
    }
  }
  cout << f(l) / 2 << '\n';
  return 0;
}

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