oj.uz

Submission #1039713

# Submission time Handle Problem Language Result Execution time Memory
1039713 2024-07-31T08:05:42 Z 라스무스 뷘터(#11030) Sprinklers (CEOI24_sprinklers) C++17
20 / 100
 2000 ms 4608 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<lint> a(n), b(m);
	for (auto &x : a)
		cin >> x;
	a.insert(a.begin(), -2e9);
	a.insert(a.end(), 3e9);
	n = sz(a);
	for (auto &x : b)
		cin >> x;
	auto trial = [&](lint x) {
		vector<vector<pi>> attach(n + 1);
		vector<int> Lmax(n + 1, -1), Rmax(n + 1, n + 1);
		for (int i = 0; i < m; i++) {
			if (binary_search(all(a), b[i]))
				continue;
			int p0 = lower_bound(all(a), b[i] - x) - a.begin();
			int p1 = lower_bound(all(a), b[i]) - a.begin();
			int p2 = upper_bound(all(a), b[i] + x) - a.begin();
			if (p0 == p1 && p1 == p2)
				return string();
			if (p0 < p1 && p1 < p2)
				attach[p1].push_back({p0, p2});
			else if (p0 < p1) {
				//	cout << p0 << " " << p1 << endl;
				// [p0 .. p1) is not all L
				Lmax[p1] = max(Lmax[p1], p0);
			} else if (p1 < p2) {
				// [p1 .. p2) is not all R
				Rmax[p1] = min(Rmax[p1], p2);
			}
		}
		for (int i = 1; i <= n; i++) {
			Lmax[i] = max(Lmax[i], Lmax[i - 1]);
		}
		for (int i = n - 1; i >= 0; i--)
			Rmax[i] = min(Rmax[i], Rmax[i + 1]);
		vector<int> dp(n + 1);
		dp[0] = 1;
		vector<pi> trace(n + 1);
		for (int i = 1; i < n; i++) {
			sort(all(attach[i]));
			int curBound = Rmax[i];
			int ptr = sz(attach[i]);
			for (int j = i - 1; j > Lmax[i]; j--) {
				while (ptr > 0 && attach[i][ptr - 1][0] == j)
					curBound = min(curBound, (int)attach[i][--ptr][1]);
				for (int k = i + 1; k < curBound; k++) {
					if (dp[j]) {
						dp[k] = 1;
						trace[k] = pi{j, i};
					}
				}
			}
		}
		if (!dp[n])
			return string();
		string ans(n, '0');
		for (int i = n; i; i = trace[i][0]) {
			for (int j = trace[i][0]; j < trace[i][1]; j++)
				ans[j] = 'L';
			for (int j = trace[i][1]; j < i; j++)
				ans[j] = 'R';
		}
		ans = ans.substr(1, n - 2);
		return ans;
	};
	int s = 0, e = 1e9 + 69;
	// int s = 1000, e = 1000;
	while (s != e) {
		int m = (s + e) / 2;
		if (sz(trial(m)))
			e = m;
		else
			s = m + 1;
	}
	if (s > int(1e9))
		cout << "-1\n";
	else {
		cout << s << "\n";
		cout << trial(s) << "\n";
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 28 ms 1884 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 71 ms 2140 KB Correct
5 Correct 39 ms 2128 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 7 ms 732 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 655 ms 4444 KB Correct
3 Execution timed out 2091 ms 1492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 1 ms 348 KB Correct
4 Correct 1 ms 348 KB Correct
5 Correct 1 ms 348 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 348 KB Correct
9 Correct 1 ms 348 KB Correct
10 Correct 1 ms 348 KB Correct
11 Correct 0 ms 348 KB Correct
12 Correct 1 ms 348 KB Correct
13 Correct 1 ms 348 KB Correct
14 Correct 1 ms 348 KB Correct
15 Correct 1 ms 348 KB Correct
16 Correct 1 ms 348 KB Correct
17 Correct 1 ms 348 KB Correct
18 Correct 1 ms 348 KB Correct
19 Correct 1 ms 348 KB Correct
20 Correct 1 ms 348 KB Correct

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Execution timed out 2019 ms 4608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 28 ms 1884 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 71 ms 2140 KB Correct
6 Correct 39 ms 2128 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 7 ms 732 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 655 ms 4444 KB Correct
12 Execution timed out 2091 ms 1492 KB Time limit exceeded
13 Halted 0 ms 0 KB -