oj.uz

Submission #1077253

# Submission time Handle Problem Language Result Execution time Memory
1077253 2024-08-27T04:08:56 Z pawned Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 7808 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Correct
2 Correct 1 ms 1884 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Correct
2 Correct 536 ms 6748 KB Correct
3 Correct 1 ms 1880 KB Correct
4 Correct 660 ms 7688 KB Correct
5 Correct 661 ms 7512 KB Correct
6 Correct 1 ms 1880 KB Correct
7 Correct 1 ms 1884 KB Correct
8 Correct 92 ms 3112 KB Correct
9 Correct 1 ms 1880 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Correct
2 Execution timed out 2007 ms 7680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Correct
2 Correct 1 ms 1884 KB Correct
3 Correct 9 ms 1880 KB Correct
4 Correct 3 ms 1884 KB Correct
5 Correct 10 ms 2100 KB Correct
6 Correct 52 ms 1884 KB Correct
7 Correct 2 ms 1880 KB Correct
8 Correct 204 ms 2068 KB Correct
9 Correct 147 ms 1884 KB Correct
10 Correct 5 ms 2136 KB Correct
11 Correct 16 ms 1880 KB Correct
12 Correct 6 ms 1880 KB Correct
13 Correct 12 ms 1884 KB Correct
14 Correct 3 ms 2052 KB Correct
15 Correct 17 ms 1884 KB Correct
16 Correct 19 ms 1884 KB Correct
17 Correct 26 ms 1884 KB Correct
18 Correct 7 ms 1884 KB Correct
19 Correct 3 ms 1884 KB Correct
20 Correct 4 ms 1884 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Correct
2 Execution timed out 2064 ms 7808 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Correct
2 Correct 1 ms 1884 KB Correct
3 Correct 536 ms 6748 KB Correct
4 Correct 1 ms 1880 KB Correct
5 Correct 660 ms 7688 KB Correct
6 Correct 661 ms 7512 KB Correct
7 Correct 1 ms 1880 KB Correct
8 Correct 1 ms 1884 KB Correct
9 Correct 92 ms 3112 KB Correct
10 Correct 1 ms 1880 KB Correct
11 Execution timed out 2007 ms 7680 KB Time limit exceeded
12 Halted 0 ms 0 KB -