Submission #1077253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077253		pawned	Sprinklers (CEOI24_sprinklers)	C++17	20 / 100	2064 ms	7808 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 < (1 << N); i++) {
		string dir;
		for (int j = 0; j < N; j++) {
			if (i & (1 << j))
				dir += 'L';
			else
				dir += 'R';
		}
		// check if all covered
		bool works = true;
		for (int j = 0; j < M; j++) {
			bool covered = false;
			for (int k = 0; k < N; k++) {
				ll lb = a[k];
				ll ub = a[k];
				if (dir[k] == 'L')
					lb -= K;
				else
					ub += K;
				if (lb <= b[j] && b[j] <= ub)
					covered = true;
			}
			if (!covered) {
				works = false;
				break;
			}
		}
		if (works)
			return dir;
	}
	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;
}

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