제출 #1226598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226598		franuch	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	47 ms	2960 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
#define st first
#define nd second
#define pll pair<ll, ll>
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define pub push_back
#define pob pop_back

ll n, m;
vc<ll> a, b;
string str;

void input() {
	cin >> n >> m;
	a.resize(n);
	b.resize(m);
	for (ll &ai : a)
		cin >> ai;
	for (ll &bi : b)
		cin >> bi;
}

bool check(ll k) {
	queue<ll> q;
	for (ll &bi : b)
		q.push(bi);
	str.clear();
	for (ll i = 0; i < n; i++) {
		ll l, r;
		if (q.empty() or a[i] <= q.front()) {
			str.pub('R');
			l = a[i];
			r = a[i] + k;
		} else if (a[i] - k <= q.front()) {
			str.pub('L');
			l = a[i] - k;
			r = a[i];
		} else
			return false;

		while (not q.empty() and l <= q.front() and q.front() <= r)
			q.pop();
	}
	return q.empty();
}

ll binsearch() {
	ll l = 0, r = 1e9 + 1;
	while (l < r) {
		ll mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	if (l == ll(1e9 + 1))
		return -1;
	return l;
}

void program() {
	input();
	ll ans = binsearch();
	cout << ans << "\n";
	if (ans == -1)
		return;
	check(ans);
	cout << str << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	return 0;
}

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