제출 #1208168

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

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back

using str = string;
template<class T> using V = vector<T>;
// template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
using vs = V<str>;
using vi = V<int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;
	vi A(N); for(auto& x : A) cin >> x;
	vi B(M); for(auto& x : B) cin >> x;

	set<int> has(begin(A), end(A));
	{
		vi C; for(auto& x : B) if (!has.count(x)) C.pb(x);
		B = C; 
	}

	M = sz(B);

	// if (A[0] > B.front() && A[0] < B.back()) {
	// 	cout << -1 << nl;
	// 	exit(0-0);
	// }	

	// if (A[0] > B.front()) cout << A[0] - B.front() << nl << "L" << nl;
	// else cout << B.back() - A[0] << nl << "R" << nl;
	// exit(0-0);

	auto chk = [&](int k) {

		str ans(N, 'L'); int j = 0;
		for(int i = 0; i < N && j < M; i++) {
			// cout << A[i] << " " << B[j] << endl;
			if (B[j] < A[i] && A[i] - B[j] <= k) {
				ans[i] = 'L';
				while(j < M && B[j] < A[i] && A[i] - B[j] <= k) j++;
			} else if (A[i] < B[j] && B[j] - A[i] <= k) {
				ans[i] = 'R';
				while(j < M && A[i] < B[j] && B[j] - A[i] <= k) j++;
			}
		}	

		if (j != M) return str("-1");
		return ans;
	};

	int lo = 0, hi = 1e9 + 10;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		// cout << mid << endl;
		if (chk(mid) != "-1") hi = mid;
		else lo = mid + 1;
	}


	str ans = chk(lo);
	if (ans != "-1") {
		cout << lo << nl;
		// assert(lo == max(abs(A.front() - B.front()), abs(A.front() - B.back())));
	}
	cout << ans << nl;

	exit(0-0);
}

// Breathe In, Breathe Out

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