Submission #1077248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077248		pawned	Sprinklers (CEOI24_sprinklers)	C++17	9 / 100	1076 ms	8108 KiB

Main

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

const int MAX = 1e5 + 5;

int N, M;

vector<ll> a(MAX);	// sprinklers
vector<ll> b(MAX);	// flowers

string check(ll K) {	// width is K
	multiset<ll> all;
	for (int i = 0; i < M; i++) {
		all.insert(b[i]);
	}
	string res = "";
	for (int i = 0; i < N; i++) {
//		cout<<"at "<<i<<endl;
		if (all.size() == 0)
			break;
		auto it = all.begin();
		ll val = (*it);	// leftmost flower
//		cout<<"val: "<<val<<endl;
		if (val < a[i] - K)
			return "!";
		if (val < a[i]) {
			// cover all from a[i]-K to a[i]
			while (all.size() > 0 && (*(all.begin())) <= a[i])
				all.erase(*(all.begin()));
			res += 'L';
		}
		else {
			while (all.size() > 0 && (*(all.begin())) <= a[i] + K)
				all.erase(*(all.begin()));
			res += 'R';
		}
/*		cout<<"remaining: ";
		for (ll x : all)
			cout<<x<<" ";
		cout<<endl;*/
	}
//	cout<<"res: "<<res<<endl;
	while (res.size() < N)
		res += 'L';
	if (all.size() == 0)
		return res;
	return "!";
}

int main() {
	fastIO();
	cin>>N>>M;
	for (int i = 0; i < N; i++) {
		cin>>a[i];
	}
	for (int i = 0; i < M; i++) {
		cin>>b[i];
	}
//	cout<<check(6)<<endl;
	ll low = 0;
	ll high = 1e18;
	ll ans = -1;	// minimum radius to water all flowers
	string ansr = "";
	while (low <= high) {	// false, false, false, true, true, true
		ll mid = (low + high) / 2;
		string res = check(mid);
		if (res != "!") {
			ans = mid;
			ansr = res;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
//	cout<<"ANSWER: ";
	cout<<ans<<endl;
	if (ans != -1)
		cout<<ansr<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'std::string check(ll)':
Main.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |  while (res.size() < N)
      |         ~~~~~~~~~~~^~~

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