제출 #1037721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037721		MilosMilutinovic	Sprinklers (CEOI24_sprinklers)	C++14	100 / 100	127 ms	4144 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  vector<int> f(m);
  for (int i = 0; i < m; i++) {
    cin >> f[i];
  }
  auto Check = [&](int k) {
    vector<int> dp(n + 1, -1);
    for (int i = 0; i < n; i++) {
      if (dp[i] == m - 1) {
        break;
      }
      if (i + 1 < n) {
        // take anything
        dp[i + 1] = max(dp[i + 1], dp[i]);
      }
      if (f[dp[i] + 1] >= s[i] - k && f[dp[i] + 1] <= s[i]) {
        // L
        int from = (int) (lower_bound(f.begin(), f.end(), s[i] - k) - f.begin());
        int to = (int) (lower_bound(f.begin(), f.end(), s[i] + 1) - f.begin()) - 1;
        dp[i + 1] = max(dp[i + 1], to);
      }
      if (f[dp[i] + 1] >= s[i] && f[dp[i] + 1] <= s[i] + k) {
        // R
        int from = (int) (lower_bound(f.begin(), f.end(), s[i]) - f.begin());
        int to = (int) (lower_bound(f.begin(), f.end(), s[i] + k + 1) - f.begin()) - 1;
        dp[i + 1] = max(dp[i + 1], to);
      }
      if (i + 1 < n && f[dp[i] + 1] >= s[i + 1] - k && f[dp[i] + 1] <= s[i + 1]) {
        // RL
        int from = (int) (lower_bound(f.begin(), f.end(), s[i + 1] - k) - f.begin());
        int to = (int) (lower_bound(f.begin(), f.end(), s[i + 1] + 1) - f.begin()) - 1;
        if (to == m - 1) {
          dp[i + 2] = max(dp[i + 2], m - 1);
          continue;
        }
        if (f[to + 1] >= s[i] && f[to + 1] <= s[i] + k) {
          to = (int) (lower_bound(f.begin(), f.end(), s[i] + k + 1) - f.begin()) - 1;
          dp[i + 2] = max(dp[i + 2], to);
        }
      }
    }
    return *max_element(dp.begin(), dp.end()) == m - 1;
  };
  int low = 0, high = 1e9, k = -1;
  while (low <= high) {
    int mid = (low + high) >> 1;
    if (Check(mid)) {
      k = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  if (k == -1) {
    cout << k << '\n';
    return 0;
  }
  vector<int> dp(n + 1, -1);
  vector<int> d(n + 1);
  auto Update = [&](int p, int v, int t) {
    if (dp[p] < v) {
      dp[p] = v;
      d[p] = t;
    }
  };
  for (int i = 0; i < n; i++) {
    if (dp[i] == m - 1) {
      Update(i + 1, dp[i], 0);
      continue;
    }
    if (i + 1 < n) {
      // take anything
      Update(i + 1, dp[i], 0);
    }
    if (f[dp[i] + 1] >= s[i] - k && f[dp[i] + 1] <= s[i]) {
      // L
      int from = (int) (lower_bound(f.begin(), f.end(), s[i] - k) - f.begin());
      int to = (int) (lower_bound(f.begin(), f.end(), s[i] + 1) - f.begin()) - 1;
      Update(i + 1, to, 0);
    }
    if (f[dp[i] + 1] >= s[i] && f[dp[i] + 1] <= s[i] + k) {
      // R
      int from = (int) (lower_bound(f.begin(), f.end(), s[i]) - f.begin());
      int to = (int) (lower_bound(f.begin(), f.end(), s[i] + k + 1) - f.begin()) - 1;
      Update(i + 1, to, 1);
    }
    if (i + 1 < n && f[dp[i] + 1] >= s[i + 1] - k && f[dp[i] + 1] <= s[i + 1]) {
      // RL
      int from = (int) (lower_bound(f.begin(), f.end(), s[i + 1] - k) - f.begin());
      int to = (int) (lower_bound(f.begin(), f.end(), s[i + 1] + 1) - f.begin()) - 1;
      if (to == m - 1) {
        Update(i + 2, m - 1, 2);
        continue;
      }
      if (f[to + 1] >= s[i] && f[to + 1] <= s[i] + k) {
        to = (int) (lower_bound(f.begin(), f.end(), s[i] + k + 1) - f.begin()) - 1;
        Update(i + 2, to, 2);
      }
    }
  }
  vector<char> dir(n);
  int p = n;
  while (p > 0) {
    if (d[p] == 0) {
      --p;
      dir[p] = 'L';
    } else if (d[p] == 1) {
      --p;
      dir[p] = 'R';
    } else {
      --p;
      dir[p] = 'L';
      --p;
      dir[p] = 'R';
    }
  }
  cout << k << '\n';
  for (int i = 0; i < n; i++) {
    cout << dir[i];
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In lambda function:
Main.cpp:30:13: warning: unused variable 'from' [-Wunused-variable]
   30 |         int from = (int) (lower_bound(f.begin(), f.end(), s[i] - k) - f.begin());
      |             ^~~~
Main.cpp:36:13: warning: unused variable 'from' [-Wunused-variable]
   36 |         int from = (int) (lower_bound(f.begin(), f.end(), s[i]) - f.begin());
      |             ^~~~
Main.cpp:42:13: warning: unused variable 'from' [-Wunused-variable]
   42 |         int from = (int) (lower_bound(f.begin(), f.end(), s[i + 1] - k) - f.begin());
      |             ^~~~
Main.cpp: In function 'int main()':
Main.cpp:89:11: warning: unused variable 'from' [-Wunused-variable]
   89 |       int from = (int) (lower_bound(f.begin(), f.end(), s[i] - k) - f.begin());
      |           ^~~~
Main.cpp:95:11: warning: unused variable 'from' [-Wunused-variable]
   95 |       int from = (int) (lower_bound(f.begin(), f.end(), s[i]) - f.begin());
      |           ^~~~
Main.cpp:101:11: warning: unused variable 'from' [-Wunused-variable]
  101 |       int from = (int) (lower_bound(f.begin(), f.end(), s[i + 1] - k) - f.begin());
      |           ^~~~

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