Submission #1196667

#TimeUsernameProblemLanguageResultExecution timeMemory
1196667mmaitiSprinklers (CEOI24_sprinklers)C++20
0 / 100
7 ms1348 KiB
#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; while (fix < M) { // flowers on the right still but no more sprinklers if (six >= N) return false; // sprinklers to the left of a flower should always be pointed right if (S[six] < F[fix]) { conf[fix] = 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 { 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; } } 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(); }
#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...