Submission #1114464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114464		dynam1c	Sprinklers (CEOI24_sprinklers)	C++17	0 / 100	88 ms	1844 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);
    vector<int> x(n+1);
    x[0] = -1;
    int j = 0;
    int li = -1, lj;
    for (int i = 0; i < n; i++) {
      if (s[i] <= x[i])
        x[i+1] = s[i]+k, d[i] = 'R';
      else if (f[j] < s[i]) {
        if (s[i]-f[j] > k)
          return false;
        x[i+1] = s[i], d[i] = 'L';
        if (li >= 0 && s[i]-k <= f[lj]) {
          x[i+1] = s[li]+k;
          d[li] = 'R';
        }
        li = i, lj = j;
      } else
        x[i+1] = s[i]+k, d[i] = 'R';
      while (j < m && f[j] <= x[i+1])
        j++;
    }
    if (j == m)
      for (char c : d)
        assert(c);
    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;
  }
  cout << r << endl;
  for (char c : d)
    cout << c;
  cout << endl;
}

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