Submission #1140766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140766		MuhammadSaram	Sprinklers (CEOI24_sprinklers)	C++20	20 / 100	2094 ms	10192 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	int a[n],b[m];
	for (int i=0;i<n;i++)
		cin>>a[i];
	for (int i=0;i<m;i++)
		cin>>b[i];
	set<int> se,se1;
	for (int i=0;i<m;i++)
		se1.insert(b[i]);
	int s=-1,e=1e9+1;
	while (s+1<e)
	{
		int mid=(s+e)/2;
		bool pos=0;
		for (int ma=0;ma<(1<<n);ma++)
		{
			se=se1;	
			for (int i=0;i<n;i++)
			{
				if ((1<<i)&ma)
				{
					while (1)
					{
						auto it=se.lower_bound(a[i]-mid);
						if (it==se.end() or *it>a[i])
							break;
						se.erase(it);
					}
				}
				else
				{
					while (1)
					{
						auto it=se.lower_bound(a[i]);
						if (it==se.end() or *it>a[i]+mid)
							break;
						se.erase(it);
					}
				}
			}
			if (se.empty())
				pos=1;
		}
		if (pos)
			e=mid;
		else
			s=mid;
	}
	if (e==1e9+1)
		e=-1;
	cout<<e<<endl;
	if (e!=-1)
	{
		for (int ma=0;ma<(1<<n);ma++)
		{
			se=se1;	
			for (int i=0;i<n;i++)
			{
				if ((1<<i)&ma)
				{
					while (1)
					{
						auto it=se.lower_bound(a[i]-e);
						if (it==se.end() or *it>a[i])
							break;
						se.erase(it);
					}
				}
				else
				{
					while (1)
					{
						auto it=se.lower_bound(a[i]);
						if (it==se.end() or *it>a[i]+e)
							break;
						se.erase(it);
					}
				}
			}
			if (se.empty())
			{
				for (int i=0;i<n;i++)
					if ((1<<i)&ma)
						cout<<'L';
					else
						cout<<'R';
				cout<<endl;
				return 0;
			}
		}
	}
	
	return 0;
}

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