Submission #1335285

#TimeUsernameProblemLanguageResultExecution timeMemory
1335285WH8Sprinklers (CEOI24_sprinklers)C++17
26 / 100
522 ms3548 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);
	auto solve=[&](int k) -> bool {
		fill(dp.begin(),dp.end(),0);
		fill(prv.begin(),prv.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]=0;
			if(dp[i-1] >= bef[i]){
				dp[i]=r[i], prv[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-1]=1;
					prv[i]=0;
				}
			}
		}
		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);
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++){
		if(prv[i]==0)cout<<'L';
		else cout << 'R';
	}
}
#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...