oj.uz

Submission #1039671

# Submission time Handle Problem Language Result Execution time Memory
1039671 2024-07-31T07:24:46 Z 라스무스 뷘터(#11030) Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 2000 ms 4384 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(), -1.1e9);
	a.insert(a.end(), 2.1e9);
	for (auto &x : b)
		cin >> x;
	auto trial = [&](lint x) {
		vector<int> L(n + 2), R(n + 2);
		vector<lint> uncoverL(n + 2, -1e11), uncoverR(n + 2, -1e11);
		vector<lint> vl, vr;
		{
			int p = 0;
			for (int i = 0; i < m; i++) {
				while (p < sz(a) && a[p] < b[i])
					p++;
				if (p == sz(a) || b[i] < a[p] - x)
					vl.push_back(b[i]);
			}
		}
		{
			int p = 0;
			for (int i = 0; i < m; i++) {
				while (p < sz(a) && a[p] + x < b[i])
					p++;
				if (p == sz(a) || b[i] < a[p])
					vr.push_back(b[i]);
			}
		}
		{
			int p = 0;
			for (int i = 1; i <= n + 1; i++) {
				while (p < sz(vl) && vl[p] < a[i])
					p++;
				if (p > 0)
					uncoverL[i] = vl[p - 1];
			}
		}
		{
			int p = 0;
			for (int i = 1; i <= n + 1; i++) {
				while (p < sz(vr) && vr[p] < a[i] + x)
					p++;
				if (p > 0)
					uncoverR[i] = vr[p - 1];
			}
		}
		L[0] = R[0] = 1;
		auto nie = [&](lint l, lint r) {
			auto it = lower_bound(all(b), l);
			return it == b.end() || *it > r;
		};
		vector<int> nxtL(n + 2), nxtR(n + 2);
		for (int i = 1; i <= n + 1; i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (uncoverL[i] <= a[j] + x && R[j]) {
					L[i] = 1;
					nxtL[i] = j;
				}
			}
			for (int j = i - 1; j >= 0; j--) {
				if (uncoverR[i] <= a[j] && nie(a[j] + 1, a[j + 1] - 1) && L[j]) {
					R[i] = 1;
					nxtR[i] = j;
				}
			}
		}
		if (!R[n + 1] && !L[n + 1])
			return string();
		string ans(n + 1, 'L');
		int pos = n + 1;
		int stat = (R[n + 1] ? 1 : 0);
		while (pos > 0) {
			//	cout << pos << " " << stat << endl;
			assert(stat ? R[pos] : L[pos]);
			int nxt = (stat ? nxtR[pos] : nxtL[pos]);
			if (stat) {
				for (int j = nxt + 1; j <= pos; j++) {
					ans[j - 1] = 'R';
				}
			}
			stat ^= 1;
			pos = nxt;
		}
		ans.pop_back();
		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 456 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Correct
2 Correct 40 ms 3692 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 37 ms 3596 KB Correct
5 Correct 36 ms 3572 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 9 ms 1212 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 85 ms 4384 KB Correct
3 Execution timed out 2027 ms 960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 0 ms 456 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 0 ms 348 KB Correct
5 Incorrect 0 ms 348 KB User solution is worse than jury's solution
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Execution timed out 2064 ms 2652 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 456 KB Correct
3 Correct 40 ms 3692 KB Correct
4 Correct 1 ms 344 KB Correct
5 Correct 37 ms 3596 KB Correct
6 Correct 36 ms 3572 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 9 ms 1212 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 85 ms 4384 KB Correct
12 Execution timed out 2027 ms 960 KB Time limit exceeded
13 Halted 0 ms 0 KB -