Submission #1279920

#TimeUsernameProblemLanguageResultExecution timeMemory
1279920khanhphucscratchSprinklers (CEOI24_sprinklers)C++20
3 / 100
54 ms3980 KiB
#include<bits/stdc++.h> #define int long long using namespace std; string ansstr; bool check(int x, vector<int> a, vector<int> b) { string curstr; int maximum = -1e9; reverse(b.begin(), b.end()); for(int i = 0; i < a.size(); i++) if(a[i] < b.back()){ maximum = a[i]+x; curstr += "R"; } while(b.size() > 0){ while(a.size() > curstr.size() && a[curstr.size()] <= b.back()){ maximum = a[curstr.size()] + x; curstr += "R"; } while(b.size() > 0 && b.back() <= maximum) b.pop_back(); if(b.size() == 0) break; int nepl = b.back()+x, p = upper_bound(a.begin(), a.end(), nepl) - a.begin() - 1; if(p < curstr.size() || p > a.size()) return 0; int lastval = -1; while(b.size() > 0 && b.back() <= a[p]){ lastval = b.back(); b.pop_back(); } while(a.size() > curstr.size() && a[curstr.size()] < lastval){ maximum = a[curstr.size()]+x; curstr += "R"; } curstr += "L"; } ansstr = curstr; return 1; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin>>n>>m; vector<int> a(n), b; for(int i = 0; i < n; i++) cin>>a[i]; for(int i = 0; i < m; i++){ int x; cin>>x; if(x > a.back() || *lower_bound(a.begin(), a.end(), x) != x) b.push_back(x); } int l = 0, r = 1e9, ans = -1; string str; while(l <= r){ int mid = (l+r)/2; if(check(mid, a, b) == 1){ans = mid; r = mid-1;} else l = mid+1; } cout<<ans<<'\n'; if(ans > -1) cout<<ansstr; }
#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...