Submission #1125889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125889		emptypringlescan	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	127 ms	4468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	long long arr[n],brr[m];
	for(int i=0; i<n; i++) cin >> arr[i];
	for(int i=0; i<m; i++) cin >> brr[i];
	long long lo=0,hi=1e9+5,mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		pair<int,int> l[n+1],r[n+1];
		int c1=0,c2=-1,c3=0,c4=-1;
		for(int i=0; i<n; i++){
			while(c1<m&&brr[c1]<arr[i]-mid) c1++;
			while(c2+1<m&&brr[c2+1]<=arr[i]) c2++;
			while(c3<m&&brr[c3]<arr[i]) c3++;
			while(c4+1<m&&brr[c4+1]<=arr[i]+mid) c4++;
			l[i+1]={c1,c2}; r[i+1]={c3,c4};
		}
		int dp[n+1];
		memset(dp,-1,sizeof(dp));
		for(int i=1; i<=n; i++){
			//R
			if(dp[i-1]+1>=r[i].first) dp[i]=max(dp[i],r[i].second);
			//L in general
			if(dp[i-1]+1>=l[i].first) dp[i]=max(dp[i],l[i].second);
			//RL
			if(i>1&&dp[i-2]+1>=l[i].first) dp[i]=max(dp[i],r[i-1].second);
		}
		if(dp[n]>=m-1) hi=mid;
		else lo=mid+1;
	}
	if(lo>1e9){
		cout << -1;
		return 0;
	}
	cout << lo << '\n';
	mid=lo;
	pair<int,int> l[n+1],r[n+1];
	int c1=0,c2=-1,c3=0,c4=-1;
	for(int i=0; i<n; i++){
		while(c1<m&&brr[c1]<arr[i]-mid) c1++;
		while(c2+1<m&&brr[c2+1]<=arr[i]) c2++;
		while(c3<m&&brr[c3]<arr[i]) c3++;
		while(c4+1<m&&brr[c4+1]<=arr[i]+mid) c4++;
		l[i+1]={c1,c2}; r[i+1]={c3,c4};
	}
	int dp[n+1],st[n+1];
	memset(dp,-1,sizeof(dp));
	for(int i=1; i<=n; i++){
		//R
		if(dp[i-1]+1>=r[i].first&&dp[i]<r[i].second){
			dp[i]=r[i].second;
			st[i]=1;
		}
		//L in general
		if(dp[i-1]+1>=l[i].first&&dp[i]<l[i].second){
			dp[i]=l[i].second;
			st[i]=2;
		}
		//RL
		if(i>1&&dp[i-2]+1>=l[i].first&&dp[i]<r[i-1].second){
			dp[i]=r[i-1].second;
			st[i]=3;
		}
	}
	char ans[n+1];
	int cur=n;
	while(cur>=1){
		if(st[cur]==1){
			ans[cur]='R';
			cur--;
		}
		else if(st[cur]==2){
			ans[cur]='L';
			cur--;
		}
		else{
			ans[cur]='L';
			ans[cur-1]='R';
			cur-=2;
		}
	}
	for(int i=1; i<=n; i++) cout << ans[i];
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 27 / 27
• Subtask 5: 47 / 47