Submission #1345301

#TimeUsernameProblemLanguageResultExecution timeMemory
1345301thelegendary08Sprinklers (CEOI24_sprinklers)C++17
26 / 100
109 ms10780 KiB
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define vi vector<int>
#define pii pair<int,int>
#define out(x) cout<<x<<'\n'
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
#define vout(v) cout<<#v<<": "; for(auto u : v)cout<<u<<' '; cout<<endl
using namespace std; 
const int mxn = 1e5 + 5;
int n,m; vi a,b; vector<pii>w; 
string solve(int k){
	vi x, y; bool ok = 1; string ans; f0r(i,n+m){
		if(i > 0 && w[i].S == 0 && w[i-1].S == 0){
			int ptr = 0; bool skip = 0; f0r(j,x.size()){
				if(skip){skip=0; continue;}
				if(ptr == y.size())ans+='L'; else if(y[ptr] > x[j]){
					ans += 'R'; while(ptr < y.size() && y[ptr] <= x[j] + k)ptr++; 
				} else{
					if(j < x.size() - 1 && x[j+1] - k <= y[ptr]){
						while(ptr < y.size() && y[ptr] <= x[j] + k)ptr++; skip=1; ans += "RL";
					}
					else if(y[ptr] < x[j] - k){
						ok = 0; break; 
					} 
					else{
						while(ptr < y.size() && y[ptr] <= x[j])ptr++; ans += 'L';
					}
				}
			}
			if(ptr < y.size())ok = 0; 
			x.clear(),y.clear(); 
		}
		if(w[i].S == 0)x.pb(w[i].F); else y.pb(w[i].F);
	}
	int ptr = 0; bool skip = 0; f0r(j,x.size()){
		if(skip){skip=0; continue;}
		if(ptr == y.size())ans+='L'; else if(y[ptr] > x[j]){
			ans += 'R'; while(ptr < y.size() && y[ptr] <= x[j] + k)ptr++; 
		} else{
			if(j < x.size() - 1 && x[j+1] - k <= y[ptr]){
				while(ptr < y.size() && y[ptr] <= x[j] + k)ptr++; skip=1; ans += "RL";
			}
			else if(y[ptr] < x[j] - k){
				ok = 0; break; 
			} 
			else{
				while(ptr < y.size() && y[ptr] <= x[j])ptr++; ans += 'L';
			}
		}
	}
	if(ptr < y.size())ok = 0; 
	x.clear(),y.clear(); 
	
	if(ok)return ans; else return "G"; 
}
signed main(){
	cin>>n>>m; a.resize(n); set<int>s; f0r(i,n)cin>>a[i],s.insert(a[i]); f0r(i,m){int x; cin>>x; if(!s.count(x))b.pb(x);}  
	m = b.size(); f0r(i,n)w.eb(a[i],0); f0r(i,m)w.eb(b[i],1); 
	sort(w.begin(),w.end()); int lo = 0, hi = 1e9 + 5; while(lo < hi){
		int mid = lo + (hi - lo) / 2; string s = solve(mid); if(s[0]=='G')lo=mid+1; else hi=mid;
	} 
	if(lo == 1e9+5)out(-1); else{
		string ans = solve(lo); out(lo); out(ans); 
	}
}
#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...