Submission #1192391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192391		LucaLucaM	Sprinklers (CEOI24_sprinklers)	C++20	20 / 100	2096 ms	840 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n, m;
  std::cin >> n >> m;

  std::vector<int> s(n), f(m);
  for (int &x : s) {
    std::cin >> x;
  }
  for (int &x : f) {
    std::cin >> x;
  }

  std::vector<char> type(n);
  
  auto check = [&](int K) {
    std::vector<bool> watered(m, false);

    for (int i = 0, j = 0; i < n; i++) {
      while (j < m && watered[j]) {
        j++;
      }
      if (j == m) {
        type[i] = 'L';
        continue;
      }
      if (f[j] < s[i]) {
        type[i] = 'L';
        //  ma pun spre stanga
        if (f[j] < s[i] - K) {
          return false;
        }
        while (j < m && f[j] <= s[i]) {
          watered[j] = true;
          j++;
        }
      } else {
        type[i] = 'R';
        // ma pun spre dreapta
        while (j < m && f[j] <= s[i] + K) {
          watered[j] = true;
          j++;
        }
      }
    }
    return std::count(watered.begin(), watered.end(), true) == m;
  };

  auto check_brute = [&](int K) {
    for (int mask = 0; mask < (1 << n); mask++) {
      std::vector<bool> watered(m, false);

      for (int i = 0; i < n; i++) {
        if (mask >> i & 1) { // L
          type[i] = 'L';
          for (int j = 0; j < m; j++) {
            if (s[i] - K <= f[j] && f[j] <= s[i]) {
              watered[j] = true;
            }
          }
        } else { // R
          type[i] = 'R';
          for (int j = 0; j < m; j++) {
            if (s[i] <= f[j] && f[j] <= s[i] + K) {
              watered[j] = true;
            }
          }
        }
      }
      if (std::count(watered.begin(), watered.end(), true) == m) {
        return true;
      }
    }
    return false;
  };

  if (!check_brute(1e9 + 1)) {
    std::cout << -1;
    return 0;
  }

  int l = 0, r = 1e9;
  while (l < r) {
    int mid = (l + r) / 2;
    if (check_brute(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  check_brute(r);
  std::cout << r << '\n';
  for (char c : type) {
    std::cout << c;
  }
  
  return 0;
}

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