Submission #1100584

#TimeUsernameProblemLanguageResultExecution timeMemory
1100584crafticatSprinklers (CEOI24_sprinklers)C++17
6 / 100
897 ms12148 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> using V = vector<T>; using vi = V<int>; using vb = V<bool>; using pi = pair<int,int>; vi water, flowers; V<bool> types; set<int> problems; constexpr int inf = 1e9 + 7; bool between(int l, int r) { auto it = problems.upper_bound(l); if (it == problems.end() || *it >= r) return true; return false; } int pos(V<V<int>> &dp, int i, int lastR, int r) { int leftR = -1; if (i >= 0) { for (int j = 0; j < 3; ++j) { if (j == 0) leftR = water[i]; if (j == 1 && i - 1 >= 0) leftR = water[i - 1] + r; if (j == 2) leftR = water[i] + r; if (dp[i][j] == -1) continue; if (between(leftR, lastR)) return j; } } else { return between(0, lastR) ? 0 : -1; } return -1; } bool ok(int r) { V<V<int>> dp(water.size() + 1, vi(3,-1)); for (int i = 0; i < water.size(); ++i) { for (int j = 0; j < 3; ++j) { int lastR = -1; if (j == 0) lastR = water[i] - r; if (j == 1 && between(water[i - 1] + r, water[i] - r)) lastR = water[i] - r; if (j == 2) lastR = water[i]; dp[i][j] = pos(dp,i - 1 + (j == 1 ? -1 : 0),lastR, r); } } // Backtrace int last = dp[water.size() - 1][2]; int i = water.size() - 1; if (last == -1) return false; while (last != -1) { if (last == 1) { types.push_back(false); types.push_back(true); if (i - 2 < 0) return true; last = dp[i - 2][last]; i -= 2; } else { types.push_back(last == 2); if (i - 1 < 0) return true; last = dp[i - 1][last]; i--; } } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; water.resize(n + 1); flowers.resize(m); for (int i = 0; i < n; ++i) { cin >> water[i]; water[i]++; } water[n] = inf; for (int i = 0; i < m; ++i) { cin >> flowers[i]; flowers[i]++; problems.insert(flowers[i]); } int l = 0, r = inf; // Last true while (r > l) { int mid = l + (r - l) / 2; if (ok(mid)) { r = mid; } else l = mid + 1; } types.clear(); ok(l); if (l == inf) { cout << -1; return 0; } cout << l << "\n"; types.pop_back(); std::reverse(types.begin(), types.end()); for (auto x : types) { cout << (x ? "R" : "L"); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'bool ok(int)':
Main.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < water.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...