Submission #1140678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140678		Jawad_Akbar_JJ	Sprinklers (CEOI24_sprinklers)	C++20	0 / 100	64 ms	840 KiB

Main

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 2e5;
int a[N], b[N], Mx[N], Par[N], type[N], dir[N], n, m;

void update(int i, int j, int val, int tp){
	if (Mx[j] >= val)
		return;
	Mx[j] = val;
	Par[j] = i;
	type[j] = tp;
}

bool check(int K, bool print = 0){
	for (int i=1;i<=n + 1;i++)
		Mx[i] = 1;

	for (int i=1;i<=n;i++){
		update(i-1, i, Mx[i-1], 1);
		// Mx[i] = max(Mx[i], Mx[i-1]);
		if (Mx[i] < m + 1 and b[Mx[i]] < Mx[i-1] and a[i] - K <= b[Mx[i]]){
			int u = upper_bound(b, b + m + 1, a[i]) - b;
			update(i, i + 1, u, 1);
			// Mx[i + 1] = max(Mx[i + 1], u);
		}

		if (Mx[i] < m + 1 and b[Mx[i]] >= a[i]){
			int u = upper_bound(b, b + m + 1, a[i] + K) - b;
			update(i, i + 1, u, 2);
			// Mx[i + 1] = max(Mx[i + 1], u);
		}

		if (Mx[i] < m + 1 and i < n and a[i + 1] - K <= b[Mx[i] + 1]){
			int u = upper_bound(b, b + m + 1, a[i] + K) - b;
			update(i, i + 2, u, 3);
			// Mx[i + 2] = max(Mx[i + 2], u);
		}
	}

	if (print){
		int nn = n;
		while (n){
			if (type[n] > 1)
				dir[Par[n]] = 1;
			n = Par[n];
			// cout<<n<<endl;
		}
		cout<<K<<'\n';
		for (int i=1;i<=nn;i++)
			cout<<(dir[i] ? 'R' : 'L');
		cout<<'\n';
		exit(0);
	}

	return max(Mx[n], Mx[n + 1]) >= m + 1;
}

int main(){
	cin>>n>>m;

	for (int i=1;i<=n;i++)
		cin>>a[i];
	
	for (int i=1;i<=m;i++)
		cin>>b[i];

	b[m + 1] = 2.1e9;

	if (n == 1 and a[1] > b[1] and a[1] < b[m])
		return cout<<"-1\n", 0;

	// for (int i=1;i<=10;i++)
	// 	cout<<check(i)<<'\n';

	// check(6, 1);

	int l = -1, r = 1e9 + 10;

	while (l + 1 < r){
		int mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	check(r, 1);
}

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