Submission #1114475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114475		dynam1c	Sprinklers (CEOI24_sprinklers)	C++17	9 / 100	203 ms	1352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> s(n), f(m);
  for (int& e : s)
    cin >> e;
  for (int& e : f)
    cin >> e;

  vector<char> d(n);
  auto check = [&](int k) {
    d.assign(n, 0);
    int x = -1;
    int j = 0, pj = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] <= x)
        x = s[i]+k, d[i] = 'R', pj = j;
      else if (j < m && f[j] < s[i]) {
        if (s[i]-f[j] > k)
          return false;
        x = s[i], d[i] = 'L';
        if (i > 0 && d[i-1] == 'L' && s[i]-k <= f[pj]) {
          x = s[i-1]+k;
          d[i-1] = 'R';
        }
      } else
        x = s[i]+k, d[i] = 'R', pj = j;
      while (j < m && f[j] <= x)
        j++;
    }
    return j == m;
  };

  if (!check(1e9)) {
    cout << -1 << endl;
    return 0;
  }

  int l = -1, r = 1e9;
  while (r-l > 1) {
    int m = (l+r)/2;
    if (check(m))
      r = m;
    else
      l = m;
  }

  check(r);

  for (int i = 0; i < n; i++)
    if (d[i] == 'L')
      s[i] -= r;
  sort(s.begin(), s.end());
  int j = 0;
  for (int e : s) {
    if (j == m)
      break;
    assert(e <= f[j]);
    while (j < m && f[j] <= e+r)
      j++;
  }
  //assert(j == m);

  cout << r << endl;
  for (char c : d)
    cout << c;
  cout << endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47