Submission #495318

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

monochrome

#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;
const int N = 400000 + 7;
int n;
string s;


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

  cin >> n >> s;

  function<ll(vector<int>, vector<int>)> compute = [&](vector<int> a, vector<int> b) {
    ll sol = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (min(a[i], b[i]) < min(a[j], b[j]) && min(a[j], b[j]) < max(a[i], b[i]) && max(a[i], b[i]) < max(a[j], b[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);
    }
  }

  ll sol = 0;

  for (int cnt = 0; 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