Submission #495316

#	Time	Username	Problem	Language	Result	Execution time	Memory
495316		600Mihnea	Monochrome Points (JOI20_monochrome)	C++17	25 / 100	2080 ms	332 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

const int N = 400000 + 7;
int n;
string s;


int main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> n >> s;
  assert((int) s.size() == 2 * n);

  function<int(vector<int>, vector<int>)> compute = [&] (vector<int> l, vector<int> r) {
    assert((int) l.size() == n);
    assert((int) r.size() == n);
    int sol = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= n; j++) {
        if (min(l[i], r[i]) < min(l[j], r[j]) && min(l[j], r[j]) < max(l[i], r[i]) && max(l[i], r[i]) < max(l[j], r[j])) {
          sol++;
        }
      }
    }
    return sol;
  };


  function<vector<int>(vector<int>, int)> shift = [&] (vector<int> a, int cnt) {
    vector<int> b((int) a.size());
    for (int i = 0; i < (int) a.size(); i++) {
      b[(i + cnt) % (int) a.size()] = a[i];
    }
    return b;
  };

  vector<int> a, b;
  for (int i = 0; i < 2 * n; i++) {
    if (s[i] != s[0]) {
      a.push_back(i);
    } else {
      b.push_back(i);
    }
  }


  int sol = compute(a, b);
  for (int cnt = 1; cnt < n; cnt++) {
    sol = max(sol, compute(a, shift(b, cnt)));
  }
  cout << sol << "\n";
}

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