oj.uz

Submission #1041150

# Submission time Handle Problem Language Result Execution time Memory
1041150 2024-08-01T16:07:30 Z Lucpp Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 494 ms 8580 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++){
			ll nxtf = dp[i] < m ? f[dp[i]] : inf;
			if(nxtf + len < s[i]) continue;
			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 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 5 ms 1116 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 6 ms 1152 KB Correct
5 Correct 6 ms 1116 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 604 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 12 ms 1264 KB Correct
3 Correct 36 ms 980 KB Correct
4 Correct 400 ms 6548 KB Correct
5 Correct 468 ms 6532 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Incorrect 228 ms 6544 KB Incorrect string length
9 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 348 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 0 ms 348 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 448 KB Correct
8 Correct 0 ms 464 KB Correct
9 Correct 0 ms 348 KB Correct
10 Correct 1 ms 600 KB Correct
11 Correct 0 ms 348 KB Correct
12 Correct 1 ms 348 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 0 ms 348 KB Correct
15 Incorrect 0 ms 348 KB Incorrect string length
16 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 Correct 52 ms 1748 KB Correct
3 Correct 494 ms 6508 KB Correct
4 Correct 444 ms 6536 KB Correct
5 Correct 447 ms 8576 KB Correct
6 Correct 470 ms 8580 KB Correct
7 Correct 444 ms 8328 KB Correct
8 Correct 466 ms 8580 KB Correct
9 Correct 446 ms 8436 KB Correct
10 Correct 446 ms 8580 KB Correct
11 Correct 449 ms 8340 KB Correct
12 Correct 1 ms 348 KB Correct
13 Correct 0 ms 348 KB Correct
14 Correct 310 ms 6732 KB Correct
15 Correct 338 ms 6724 KB Correct
16 Correct 315 ms 6780 KB Correct
17 Correct 385 ms 7048 KB Correct
18 Correct 385 ms 7300 KB Correct
19 Correct 403 ms 7556 KB Correct
20 Correct 445 ms 7976 KB Correct
21 Correct 447 ms 8096 KB Correct
22 Correct 493 ms 7816 KB Correct
23 Correct 464 ms 7892 KB Correct
24 Incorrect 466 ms 7704 KB Incorrect string length
25 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 5 ms 1116 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 6 ms 1152 KB Correct
6 Correct 6 ms 1116 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 1 ms 604 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 12 ms 1264 KB Correct
12 Correct 36 ms 980 KB Correct
13 Correct 400 ms 6548 KB Correct
14 Correct 468 ms 6532 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Incorrect 228 ms 6544 KB Incorrect string length
18 Halted 0 ms 0 KB -