Submission #1196671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196671		mmaiti	Sprinklers (CEOI24_sprinklers)	C++20	26 / 100	49 ms	2888 KiB

Main

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define sll set<ll>
#define usll unordered_set<ll>
#define vb vector<bool>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>

vll S;
vll F;
ll N, M;
vll conf;
bool getConf(ll power) {
  ll fix = 0, six = 0;
  // invariant is that all previous sprinklers are placed optimally and all
  // flowers before index M are watered
  while (fix < M) {
    // flowers on the right still but no more sprinklers
    if (six >= N)
      return false;
    // flowers at a sprinkler are meaningless
    if (S[six] == F[fix]) {
      fix++;
    }
    // sprinklers to the left of a flower should always be pointed right
    else if (S[six] < F[fix]) {
      conf[six] = 1;
      while (fix < M && S[six] + power >= F[fix])
        fix++;
      six++;
    } else {
      ll prevSix = six;
      // find the rightmost sprinkler that can water this flower
      while (six + 1 < N && abs(S[six + 1] - F[fix]) <= power) {
        six++;
      }
      // if the flower is too far left to begin with, we lose
      if (abs(S[six] - F[fix]) > power)
        return false;

      // have to point left
      if (prevSix == six) {
        conf[six] = 0;
        while (fix < M && F[fix] <= S[six])
          fix++;
        six++;
      }
      // if there is no flowers between cur sprinkler and sprinkler before it,
      // just use the one before.
      else if (six == prevSix + 1) {
        auto prevFlower = upper_bound(F.begin(), F.end(), S[six - 1]);
        if (prevFlower == F.end() || *prevFlower >= S[six]) {
          // we are good, can point six-1 left and six to right
          conf[prevSix] = 0;
          conf[six] = 1;
          while (fix < M && F[fix] <= S[six] + power)
            fix++;
          six++;
        } else {
          if (six + 1 < N && (S[six + 1] - *prevFlower) <= power) {
            auto nxFlower = upper_bound(F.begin(), F.end(), S[six]);
            if (nxFlower == F.end() || *nxFlower >= S[six + 1]) {
              conf[six] = 0;
              conf[prevSix] = 1;
              while (fix < M && F[fix] <= S[prevSix] + power)
                fix++;
              six++;
            } else {
              conf[prevSix] = 0;
              conf[six] = 1;
              conf[six + 1] = 0;
              while (fix < M && F[fix] <= S[six] + power) {
                fix++;
              }
              six += 2;
            }
          } else {
            conf[six] = 0;
            conf[prevSix] = 1;
            while (fix < M && F[fix] <= S[prevSix] + power)
              fix++;
            six++;
          }
        }
      }
      // point 2 before right, 1 before left, and current right
      else {
        conf[six - 2] = 1;
        conf[six - 1] = 0;
        conf[six] = 1;
        while (fix < M && F[fix] <= S[six] + power)
          fix++;
      }
    }
  }
  for (int i = 0; i < N; i++) {
    if (conf[i] == -1)
      conf[i] = 0;
  }
  return true;
}
void solve() {
  cin >> N >> M;
  S.resize(N);
  F.resize(M);
  conf.resize(N, -1);
  for (int i = 0; i < N; i++)
    cin >> S[i];
  for (int i = 0; i < M; i++)
    cin >> F[i];

  ll lo = 0;
  ll hi = 1e9 + 1;
  ll sol = hi;
  while (lo <= hi) {
    fill(conf.begin(), conf.end(), -1);
    ll mid = (lo + hi) / 2;
    if (getConf(mid)) {
      sol = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  fill(conf.begin(), conf.end(), -1);
  if (!getConf(sol)) {
    cout << -1 << "\n";
  } else {
    cout << sol << "\n";
    for (int i = 0; i < N; i++) {
      /*assert(conf[i] != -1);*/
      if (conf[i] == 0)
        cout << 'L';
      else
        cout << 'R';
    }
    cout << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  solve();
}

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