oj.uz

Submission #1114465

# Submission time Handle Problem Language Result Execution time Memory
1114465 2024-11-18T23:47:55 Z dynam1c Sprinklers (CEOI24_sprinklers) C++17
0 / 100
 104 ms 1732 KB 
#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 == 'L' || c == 'R');
    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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Incorrect 28 ms 592 KB Invalid character in the string
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 26 ms 592 KB Correct
3 Correct 6 ms 336 KB Correct
4 Correct 69 ms 1732 KB Correct
5 Correct 71 ms 1588 KB Correct
6 Correct 1 ms 336 KB Correct
7 Correct 1 ms 336 KB Correct
8 Incorrect 81 ms 1592 KB Invalid character in the string
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Incorrect 1 ms 336 KB Invalid character in the string
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 33 ms 848 KB Correct
3 Correct 104 ms 1596 KB Correct
4 Correct 94 ms 1728 KB Correct
5 Correct 89 ms 1728 KB Correct
6 Incorrect 89 ms 1732 KB User solution is incorrect
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct
2 Correct 1 ms 336 KB Correct
3 Incorrect 28 ms 592 KB Invalid character in the string
4 Halted 0 ms 0 KB -