oj.uz

Submission #1041156

# Submission time Handle Problem Language Result Execution time Memory
1041156 2024-08-01T16:13:57 Z Lucpp Sprinklers (CEOI24_sprinklers) C++17
100 / 100
 505 ms 8576 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)size(x)

constexpr ll inf = 1e9 + 10;

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<ll> s(n), f(m);
	for(ll& e : s) cin >> e;
	for(ll& e : f) cin >> e;
	auto check = [&](ll len) -> string {
		vector<int> dp(n+1, -1);
		dp[0] = 0;
		vector<pair<int, string>> prv(n+1);
		for(int i = 0; i < n; i++){
			if(dp[i] == -1) return "";
			ll nxtf = dp[i] < m ? f[dp[i]] : inf;
			if(nxtf + len < s[i]) return "";
			vector<tuple<int, int, string>> opts;
			opts.emplace_back(i+1, upper_bound(all(f), s[i]) - f.begin(), "L");
			if(nxtf >= s[i]) opts.emplace_back(i+1, upper_bound(all(f), s[i]+len) - f.begin(), "R");
			if(i < n-1 && s[i+1]-len <= nxtf) opts.emplace_back(i+2, upper_bound(all(f), s[i]+len) - f.begin(), "RL");
			for(auto [i2, x, str] : opts){
				if(dp[i2] < x){
					dp[i2] = x;
					prv[i2] = {i, str};
				}
			}
		}
		if(dp[n] < m) return "";
		int i = n;
		string rec;
		while(i > 0){
			auto [i2, str] = prv[i];
			reverse(all(str));
			rec += str;
			i = i2;
		}
		reverse(all(rec));
		return rec;
	};
	ll lo = -1, hi = inf;
	while(lo+1 < hi){
		ll mid = (lo + hi) / 2;
		if(check(mid) == "") lo = mid;
		else hi = mid;
	}
	if(hi == inf) cout << "-1\n";
	else{
		cout << hi << "\n";
		cout << check(hi) << "\n";
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 5 ms 1884 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 6 ms 1784 KB Correct
5 Correct 7 ms 1884 KB Correct
6 Correct 1 ms 344 KB Correct
7 Correct 0 ms 344 KB Correct
8 Correct 1 ms 604 KB Correct
9 Correct 0 ms 344 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 11 ms 1884 KB Correct
3 Correct 35 ms 1116 KB Correct
4 Correct 386 ms 7836 KB Correct
5 Correct 439 ms 7820 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 259 ms 7824 KB Correct
9 Correct 242 ms 7828 KB Correct
10 Correct 388 ms 7908 KB Correct
11 Correct 290 ms 6524 KB Correct
12 Correct 166 ms 4348 KB Correct
13 Correct 407 ms 7300 KB Correct
14 Correct 379 ms 7560 KB Correct
15 Correct 424 ms 7692 KB Correct
16 Correct 404 ms 7284 KB Correct

Subtask #3
17.0 / 17.0

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

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 53 ms 2528 KB Correct
3 Correct 458 ms 7700 KB Correct
4 Correct 473 ms 7816 KB Correct
5 Correct 451 ms 7940 KB Correct
6 Correct 456 ms 7944 KB Correct
7 Correct 448 ms 7812 KB Correct
8 Correct 451 ms 7904 KB Correct
9 Correct 480 ms 7744 KB Correct
10 Correct 455 ms 7920 KB Correct
11 Correct 455 ms 7860 KB Correct
12 Correct 0 ms 344 KB Correct
13 Correct 0 ms 452 KB Correct
14 Correct 317 ms 6612 KB Correct
15 Correct 352 ms 6628 KB Correct
16 Correct 332 ms 6540 KB Correct
17 Correct 393 ms 7044 KB Correct
18 Correct 413 ms 7104 KB Correct
19 Correct 418 ms 7408 KB Correct
20 Correct 448 ms 7568 KB Correct
21 Correct 455 ms 7568 KB Correct
22 Correct 492 ms 7556 KB Correct
23 Correct 461 ms 7568 KB Correct
24 Correct 466 ms 7308 KB Correct
25 Correct 468 ms 7560 KB Correct
26 Correct 297 ms 5664 KB Correct
27 Correct 173 ms 3416 KB Correct
28 Correct 431 ms 7356 KB Correct
29 Correct 424 ms 7312 KB Correct
30 Correct 505 ms 7404 KB Correct
31 Correct 371 ms 6612 KB Correct

Subtask #5
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 5 ms 1884 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 6 ms 1784 KB Correct
6 Correct 7 ms 1884 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 0 ms 344 KB Correct
9 Correct 1 ms 604 KB Correct
10 Correct 0 ms 344 KB Correct
11 Correct 11 ms 1884 KB Correct
12 Correct 35 ms 1116 KB Correct
13 Correct 386 ms 7836 KB Correct
14 Correct 439 ms 7820 KB Correct
15 Correct 0 ms 344 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 259 ms 7824 KB Correct
18 Correct 242 ms 7828 KB Correct
19 Correct 388 ms 7908 KB Correct
20 Correct 290 ms 6524 KB Correct
21 Correct 166 ms 4348 KB Correct
22 Correct 407 ms 7300 KB Correct
23 Correct 379 ms 7560 KB Correct
24 Correct 424 ms 7692 KB Correct
25 Correct 404 ms 7284 KB Correct
26 Correct 0 ms 348 KB Correct
27 Correct 0 ms 348 KB Correct
28 Correct 1 ms 344 KB Correct
29 Correct 0 ms 348 KB Correct
30 Correct 0 ms 348 KB Correct
31 Correct 0 ms 344 KB Correct
32 Correct 0 ms 348 KB Correct
33 Correct 0 ms 348 KB Correct
34 Correct 0 ms 456 KB Correct
35 Correct 0 ms 348 KB Correct
36 Correct 0 ms 604 KB Correct
37 Correct 0 ms 348 KB Correct
38 Correct 0 ms 452 KB Correct
39 Correct 0 ms 348 KB Correct
40 Correct 1 ms 348 KB Correct
41 Correct 0 ms 348 KB Correct
42 Correct 1 ms 604 KB Correct
43 Correct 0 ms 348 KB Correct
44 Correct 53 ms 2528 KB Correct
45 Correct 458 ms 7700 KB Correct
46 Correct 473 ms 7816 KB Correct
47 Correct 451 ms 7940 KB Correct
48 Correct 456 ms 7944 KB Correct
49 Correct 448 ms 7812 KB Correct
50 Correct 451 ms 7904 KB Correct
51 Correct 480 ms 7744 KB Correct
52 Correct 455 ms 7920 KB Correct
53 Correct 455 ms 7860 KB Correct
54 Correct 0 ms 344 KB Correct
55 Correct 0 ms 452 KB Correct
56 Correct 317 ms 6612 KB Correct
57 Correct 352 ms 6628 KB Correct
58 Correct 332 ms 6540 KB Correct
59 Correct 393 ms 7044 KB Correct
60 Correct 413 ms 7104 KB Correct
61 Correct 418 ms 7408 KB Correct
62 Correct 448 ms 7568 KB Correct
63 Correct 455 ms 7568 KB Correct
64 Correct 492 ms 7556 KB Correct
65 Correct 461 ms 7568 KB Correct
66 Correct 466 ms 7308 KB Correct
67 Correct 468 ms 7560 KB Correct
68 Correct 297 ms 5664 KB Correct
69 Correct 173 ms 3416 KB Correct
70 Correct 431 ms 7356 KB Correct
71 Correct 424 ms 7312 KB Correct
72 Correct 505 ms 7404 KB Correct
73 Correct 371 ms 6612 KB Correct
74 Correct 15 ms 2140 KB Correct
75 Correct 402 ms 8484 KB Correct
76 Correct 496 ms 8480 KB Correct
77 Correct 1 ms 344 KB Correct
78 Correct 153 ms 8536 KB Correct
79 Correct 422 ms 8576 KB Correct
80 Correct 164 ms 8576 KB Correct
81 Correct 314 ms 6880 KB Correct
82 Correct 329 ms 6744 KB Correct
83 Correct 303 ms 6740 KB Correct
84 Correct 31 ms 1684 KB Correct
85 Correct 455 ms 7572 KB Correct
86 Correct 463 ms 7560 KB Correct
87 Correct 380 ms 6780 KB Correct
88 Correct 6 ms 2136 KB Correct
89 Correct 7 ms 2140 KB Correct