oj.uz

Submission #1043087

# Submission time Handle Problem Language Result Execution time Memory
1043087 2024-08-03T22:48:29 Z Tob Sprinklers (CEOI24_sprinklers) C++14
9 / 100
 89 ms 7432 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7;

int n, m;
int a[N], b[N], dp[N], gt[N];
string t[N];

void update(int x, int y, int val, string s) {
	if (dp[y] < val) {
		dp[y] = val;
		gt[y] = x;
		t[y] = s;
	}
}
void check(int k) {	
	memset(dp, -1, sizeof dp);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] == -1) continue;
		if (b[dp[i]]+k >= a[i] && b[dp[i]] <= a[i]) update(i, i+1, upper_bound(b, b+m, a[i])-b, "L");
		if (b[dp[i]] >= a[i] && a[i]+k >= b[dp[i]]) update(i, i+1, upper_bound(b, b+m, a[i]+k)-b, "R");
		if (a[i]+k < b[dp[i]]) update(i, i+1, dp[i], "R");
		if (i < n-1 && b[dp[i]] < a[i] && b[dp[i]]+k >= a[i+1]) update(i, i+2, upper_bound(b, b+m, a[i]+k)-b, "RL");
	}
}

int main () {
	FIO;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];
	b[m] = 2e9 + 7;
	
	if (n == 1 && a[0] > b[0] && a[n-1] < b[m-1]) {
		cout << "-1\n";
		return 0;
	}
	
	int lo = 0, hi = 1e9;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		check(mid);
		if (dp[n] == m) hi = mid;
		else lo = mid+1;
	}
	cout << lo << "\n";
	check(lo);
	
	int x = n;
	string s;
	while (x) {
		s += t[x];
		x = gt[x];
	}
	reverse(all(s));
	cout << s;

	return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Correct
2 Correct 1 ms 4700 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Correct
2 Correct 6 ms 5372 KB Correct
3 Correct 1 ms 4700 KB Correct
4 Correct 7 ms 5724 KB Correct
5 Correct 6 ms 5628 KB Correct
6 Correct 1 ms 4696 KB Correct
7 Correct 1 ms 4700 KB Correct
8 Correct 2 ms 4700 KB Correct
9 Correct 1 ms 4700 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Correct
2 Correct 7 ms 5724 KB Correct
3 Correct 5 ms 4956 KB Correct
4 Correct 51 ms 7324 KB Correct
5 Correct 54 ms 7336 KB Correct
6 Correct 1 ms 4696 KB Correct
7 Correct 2 ms 4700 KB Correct
8 Correct 25 ms 7432 KB Correct
9 Correct 25 ms 7260 KB Correct
10 Correct 30 ms 7252 KB Correct
11 Correct 23 ms 6228 KB Correct
12 Correct 26 ms 6236 KB Correct
13 Correct 43 ms 6484 KB Correct
14 Correct 46 ms 6480 KB Correct
15 Correct 44 ms 6796 KB Correct
16 Correct 44 ms 6228 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Correct
2 Correct 1 ms 4700 KB Correct
3 Correct 1 ms 4696 KB Correct
4 Correct 1 ms 4696 KB Correct
5 Incorrect 1 ms 4700 KB User solution is incorrect
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Correct
2 Correct 25 ms 5724 KB Correct
3 Incorrect 89 ms 7320 KB User solution is incorrect
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Correct
2 Correct 1 ms 4700 KB Correct
3 Correct 6 ms 5372 KB Correct
4 Correct 1 ms 4700 KB Correct
5 Correct 7 ms 5724 KB Correct
6 Correct 6 ms 5628 KB Correct
7 Correct 1 ms 4696 KB Correct
8 Correct 1 ms 4700 KB Correct
9 Correct 2 ms 4700 KB Correct
10 Correct 1 ms 4700 KB Correct
11 Correct 7 ms 5724 KB Correct
12 Correct 5 ms 4956 KB Correct
13 Correct 51 ms 7324 KB Correct
14 Correct 54 ms 7336 KB Correct
15 Correct 1 ms 4696 KB Correct
16 Correct 2 ms 4700 KB Correct
17 Correct 25 ms 7432 KB Correct
18 Correct 25 ms 7260 KB Correct
19 Correct 30 ms 7252 KB Correct
20 Correct 23 ms 6228 KB Correct
21 Correct 26 ms 6236 KB Correct
22 Correct 43 ms 6484 KB Correct
23 Correct 46 ms 6480 KB Correct
24 Correct 44 ms 6796 KB Correct
25 Correct 44 ms 6228 KB Correct
26 Correct 1 ms 4696 KB Correct
27 Correct 1 ms 4696 KB Correct
28 Incorrect 1 ms 4700 KB User solution is incorrect
29 Halted 0 ms 0 KB -