제출 #1335293

#제출 시각아이디문제언어결과실행 시간메모리
1335293WH8Sprinklers (CEOI24_sprinklers)C++17
100 / 100
557 ms3940 KiB
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n,fn;cin>>n>>fn;
	vector<int> s(n+1, 0), f(fn+1, -1);
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=1;i<=fn;i++){
		cin>>f[i];
	}
	int hi=1e9, lo=0, ans=-1, m;
	vector<int> dp(n+1, 0), prv(n+1, 0), st(n+1, 0);
	auto solve=[&](int k) -> bool {
		fill(dp.begin(),dp.end(),0);
		fill(prv.begin(),prv.end(),0);
		fill(st.begin(),st.end(),0);
		vector<int> l(n+1, 0), r(n+1, 0), bef(n+1, 0), last(n+1, 0);
		for(int i=1;i<=n;i++){
			bef[i]=lower_bound(f.begin(),f.end(),s[i])-f.begin()-1;
			last[i]=upper_bound(f.begin(),f.end(),s[i])-f.begin()-1;
			r[i]=upper_bound(f.begin(),f.end(), s[i]+k)-f.begin()-1;
			l[i]=lower_bound(f.begin(),f.end(), s[i]-k)-f.begin();
		}
		for(int i=1;i<=n;i++){
			if (l[i] > dp[i-1] + 1) return 0;
			dp[i]=last[i], prv[i]=i-1, st[i]=0;
			if(dp[i-1] >= bef[i]){
				dp[i]=r[i], prv[i]=i-1, st[i]=1;
			}
			if(i >= 2 and dp[i-2] >= l[i]-1){
				if(r[i-1] > dp[i]){
					dp[i]=r[i-1];
					prv[i]=i-2;
					st[i]=2;
				}
			}
		}
		if(dp[n] >= fn) return 1;
		return 0;
	};
	while(hi >= lo){
		m=(hi+lo)/2;
		bool ok=solve(m);
		if(ok){
			ans=m;
			hi=m-1;
		}
		else {
			lo=m+1;
		}
	}
	if(ans == -1){
		cout<<-1;
		return 0;
	}
	solve(ans);
	vector<int> path;
	int c=n;
	while(c != 0){
		path.push_back(c);
		c = prv[c];
	}
	reverse(path.begin(),path.end());
	cout<<ans<<'\n';
	for(auto i : path){
		if(st[i]==1) cout<<'R';
		else if(st[i]==0)cout<<'L';
		else cout<<"RL";
	}
}
#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...