Submission #495311

#	Time	Username	Problem	Language	Result	Execution time	Memory
495311		600Mihnea	Monochrome Points (JOI20_monochrome)	C++17	25 / 100	2062 ms	336 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);
    for (int i = 0; i < n; i++) {
      if (l[i] > r[i]) {
        swap(l[i], r[i]);
      }
    }
    int sol = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= n; j++) {
        if (l[i] < l[j] && l[j] < r[i] && r[i] < r[j]) {
          sol++;
        }
      }
    }
    return sol;
  };

  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 shift = 1; shift < n; shift++) {
    vector<int> newB;
    for (int i = 1; i < n; i++) {
      newB.push_back(b[i]);
    }
    newB.push_back(b[0]);
    b = newB;
    sol = max(sol, compute(a, b));
  }
  cout << sol << "\n";
}

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