Submission #1114397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114397	2024-11-18T18:56:34 Z	dynam1c	Sprinklers (CEOI24_sprinklers)	C++17	0 / 100	71 ms	3656 KB

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;
    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';
      } else
        x[i+1] = s[i]+k, d[i] = 'R';
      while (j < m && f[j] <= x[i])
        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;
  }
  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	22 ms	1360 KB	User solution is worse than jury's solution
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	27 ms	1616 KB	Correct
3	Correct	6 ms	592 KB	Correct
4	Correct	67 ms	3520 KB	Correct
5	Correct	71 ms	3656 KB	Correct
6	Correct	1 ms	592 KB	Correct
7	Correct	1 ms	336 KB	Correct
8	Incorrect	59 ms	3620 KB	Invalid character in the string
9	Halted	0 ms	0 KB	-