제출 #1197279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197279		mmaiti	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	376 ms	27848 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;
// if the second element in P is not -1, then recurse 2 positions back else
// recurse 1
vector<vector<pll>> P;
bool getConf(ll power) {
  // -1 means no solution
  // dp[i][0] means sprinkler i facing left
  vector<vll> dp(N, vll(2, -1));
  P = vector<vector<pll>>(N, vector<pll>(2, {-1, -1}));
  // Set up IC for DP
  if (F[0] < S[0]) {
    if (S[0] - power <= F[0]) {
      dp[0][0] = S[0];
    } else {
      return false;
    }
  } else {
    dp[0][1] = S[0] + power;
  }

  for (int i = 1; i < N; i++) {
    auto close = lower_bound(F.begin(), F.end(), S[i]);
    // can we point this sprinkler right?
    // yes
    if (close == F.begin() || *(--close) <= max(dp[i - 1][0], dp[i - 1][1])) {
      dp[i][1] = S[i] + power;
      P[i][1] =
          dp[i - 1][1] >= dp[i - 1][0] ? make_pair(1, -1) : make_pair(0, -1);
      // no
    } else {
      // have to point left, now split into cases
      if (i >= 2 && S[i] - power <= S[i - 2]) {
        // we know dp[i-1][0 or 1] is valid, so then can point sprinkler i-1 to
        // the right
        dp[i][0] = S[i - 1] + power;
        P[i][0] =
            (dp[i - 2][1] >= dp[i - 2][0]) ? make_pair(1, 1) : make_pair(1, 0);
      } else if (S[i] - power <= S[i - 1]) {
        // want to try to point sprinkler i-1 to the right if possible
        auto nxPoint = lower_bound(F.begin(), F.end(), S[i] - power);
        if (i >= 2) {
          if (nxPoint == F.begin() ||
              *(--nxPoint) <= max(dp[i - 2][0], dp[i - 2][1])) {
            dp[i][0] = S[i - 1] + power;
            P[i][0] = (dp[i - 2][1] >= dp[i - 2][0]) ? make_pair(1, 1)
                                                     : make_pair(1, 0);
          } else {
            // turn both to the left
            dp[i][0] = S[i];
            P[i][0] = make_pair(0, -1);
          }
        } else {
          if (nxPoint == F.begin()) {
            dp[i][0] = S[i - 1] + power;
            P[i][0] = {1, -1};
          } else {
            dp[i][0] = S[i];
            P[i][0] = {0, -1};
          }
        }
      } else {
        // only in this case is there a possibility that we may not be able to
        // cover all points to the left, and thus here one branch returns false
        auto nxPoint = lower_bound(F.begin(), F.end(), S[i] - power);
        if (nxPoint == F.begin() ||
            *(--nxPoint) <= max(dp[i - 1][0], dp[i - 1][1])) {
          dp[i][0] = S[i];
          P[i][0] = (dp[i - 1][1] >= dp[i - 1][0]) ? make_pair(1, -1)
                                                   : make_pair(0, -1);
        } else {
          return false;
        }
      }
    }
  }

  return max(dp[N - 1][0], dp[N - 1][1]) >= F[F.size() - 1];
}

void printSol(int curIx, int dir) {
  if (P[curIx][dir].second != -1) {
    printSol(curIx - 2, P[curIx][dir].second);
    cout << (P[curIx][dir].first == 0 ? 'L' : 'R');
  } else if (P[curIx][dir].first != -1) {
    printSol(curIx - 1, P[curIx][dir].first);
  }
  cout << (dir == 0 ? 'L' : 'R');
}
void solve() {
  cin >> N >> M;
  S.resize(N);
  F.resize(M);
  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) {
    ll mid = (lo + hi) / 2;
    if (getConf(mid)) {
      sol = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  if (!getConf(sol)) {
    cout << -1 << "\n";
  } else {
    cout << sol << "\n";

    if (P[N - 1][0].first == -1 && P[N - 1][0].second == -1) {
      if (N == 1 && F[0] < S[0]) {
        printSol(N - 1, 0);
      } else {
        printSol(N - 1, 1);
      }
    } else {
      printSol(N - 1, 0);
    }
    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: 27 / 27
• Subtask 5: 47 / 47