oj.uz

답안 #1039700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039700 2024-07-31T07:54:59 Z 라스무스 뷘터(#11030) Sprinklers (CEOI24_sprinklers) C++17
0 / 100
 2000 ms 3676 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.begin(), 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) {
				// [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]));
			for (int j = Lmax[i] + 1; j < i; j++) {
				for (int k = i + 1; k < Rmax[i]; k++) {
					if (!binary_search(all(attach[i]), pi{j, k}) && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct

Subtask #1
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct
2 Incorrect 30 ms 1112 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Execution timed out 2102 ms 3508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Incorrect 1 ms 344 KB User solution is incorrect
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Execution timed out 2041 ms 3676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Incorrect 30 ms 1112 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -