제출 #1041156

#제출 시각아이디문제언어결과실행 시간메모리
1041156LucppSprinklers (CEOI24_sprinklers)C++17
100 / 100
505 ms8576 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)size(x)

constexpr ll inf = 1e9 + 10;

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<ll> s(n), f(m);
	for(ll& e : s) cin >> e;
	for(ll& e : f) cin >> e;
	auto check = [&](ll len) -> string {
		vector<int> dp(n+1, -1);
		dp[0] = 0;
		vector<pair<int, string>> prv(n+1);
		for(int i = 0; i < n; i++){
			if(dp[i] == -1) return "";
			ll nxtf = dp[i] < m ? f[dp[i]] : inf;
			if(nxtf + len < s[i]) return "";
			vector<tuple<int, int, string>> opts;
			opts.emplace_back(i+1, upper_bound(all(f), s[i]) - f.begin(), "L");
			if(nxtf >= s[i]) opts.emplace_back(i+1, upper_bound(all(f), s[i]+len) - f.begin(), "R");
			if(i < n-1 && s[i+1]-len <= nxtf) opts.emplace_back(i+2, upper_bound(all(f), s[i]+len) - f.begin(), "RL");
			for(auto [i2, x, str] : opts){
				if(dp[i2] < x){
					dp[i2] = x;
					prv[i2] = {i, str};
				}
			}
		}
		if(dp[n] < m) return "";
		int i = n;
		string rec;
		while(i > 0){
			auto [i2, str] = prv[i];
			reverse(all(str));
			rec += str;
			i = i2;
		}
		reverse(all(rec));
		return rec;
	};
	ll lo = -1, hi = inf;
	while(lo+1 < hi){
		ll mid = (lo + hi) / 2;
		if(check(mid) == "") lo = mid;
		else hi = mid;
	}
	if(hi == inf) cout << "-1\n";
	else{
		cout << hi << "\n";
		cout << check(hi) << "\n";
	}
}
#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...