제출 #1345318

#제출 시각아이디문제언어결과실행 시간메모리
1345318thelegendary08Sprinklers (CEOI24_sprinklers)C++17
36 / 100
135 ms10756 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){
			vector<pii>dp(x.size()+1, mp(-1,-1)); //0=L, 1=R, 2=RL
			int ptr = 0; bool skip = 0; f0r(j,x.size()){
				if(dp[j+1-1].F == (int)y.size()-1)dp[j+1]=mp((int)y.size()-1,0); 
				else{
					if(y[dp[j+1-1].F+1] > x[j]){
						int lo = dp[j+1-1].F, hi = (int)y.size()-1; while(lo < hi){
							int mid = lo + (hi - lo + 1) / 2; if(y[mid] <= x[j] + k)lo=mid; else hi=mid-1;
						}
						dp[j+1] = mp(lo, 1);
					}
					else{
						if(y[dp[j+1-1].F+1] >= x[j] - k){
							int lo = dp[j+1-1].F+1, hi = (int)y.size()-1; while(lo < hi){
								int mid = lo + (hi - lo + 1) / 2; if(y[mid] <= x[j])lo=mid; else hi=mid-1; 
							}
							dp[j+1] = max(dp[j+1], mp(lo,0LL));
						}
						if(j >= 2 && x[j] - k <= y[dp[j+1-2].F+1]){
							int lo = dp[j+1-2].F + 1, hi = (int)y.size()-1; while(lo < hi){
								int mid = lo + (hi - lo + 1) / 2; if(y[mid] <= max(x[j],x[j-1] + k))lo=mid; else hi=mid-1;
							}
							dp[j+1] = max(dp[j+1], mp(lo,2LL));
						}
					}
				}
				// 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; 
			if(dp[x.size()].F < (int)y.size() - 1)ok=0; 
			else{
				int cur = x.size(); string ass = ""; while(cur > 0){
					if(dp[cur].S == 0)ass+='L',cur--; else if(dp[cur].S == 1)ass+='R',cur--; else ass += "LR",cur-=2;
				} reverse(ass.begin(),ass.end()); ans += ass; 
			}
			x.clear(),y.clear(); 
		}
		if(w[i].S == 0)x.pb(w[i].F); else y.pb(w[i].F);
	}
	vector<pii>dp(x.size()+1, mp(-1,-1)); //0=L, 1=R, 2=RL
	int ptr = 0; bool skip = 0; f0r(j,x.size()){
		if(dp[j+1-1].F == (int)y.size()-1)dp[j+1]=mp((int)y.size()-1,0); 
		else{
			if(y[dp[j+1-1].F+1] > x[j]){
				int lo = dp[j+1-1].F, hi = (int)y.size()-1; while(lo < hi){
					int mid = lo + (hi - lo + 1) / 2; if(y[mid] <= x[j] + k)lo=mid; else hi=mid-1;
				}
				dp[j+1] = mp(lo, 1);
			}
			else{
				if(y[dp[j+1-1].F+1] >= x[j] - k){
					int lo = dp[j+1-1].F+1, hi = (int)y.size()-1; while(lo < hi){
						int mid = lo + (hi - lo + 1) / 2; if(y[mid] <= x[j])lo=mid; else hi=mid-1; 
					}
					dp[j+1] = max(dp[j+1], mp(lo,0LL));
				}
				if(j >= 1 && x[j] - k <= y[dp[j+1-2].F+1] && y[dp[j+1-2].F+1] < x[j-1]){
					int lo = dp[j+1-2].F + 1, hi = (int)y.size()-1; while(lo < hi){
						int mid = lo + (hi - lo + 1) / 2; if(y[mid] <= max(x[j],x[j-1] + k))lo=mid; else hi=mid-1;
					}
					dp[j+1] = max(dp[j+1], mp(lo,2LL));
				}
			}
		}
	}
	if(dp[x.size()].F < (int)y.size() - 1)ok=0; 
	else{
		int cur = x.size(); string ass = ""; while(cur > 0){
			if(dp[cur].S == 0)ass+='L',cur--; else if(dp[cur].S == 1)ass+='R',cur--; else ass += "LR",cur-=2;
		} reverse(ass.begin(),ass.end()); ans += ass; 
	}
	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...