oj.uz

Submission #1041127

# Submission time Handle Problem Language Result Execution time Memory
1041127 2024-08-01T15:55:04 Z Lucpp Sprinklers (CEOI24_sprinklers) C++17
3 / 100
 447 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);
		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 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 2140 KB Correct
5 Correct 6 ms 2128 KB Correct
6 Correct 1 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 1 ms 656 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 344 KB Correct
2 Correct 11 ms 2236 KB Correct
3 Correct 35 ms 1116 KB Correct
4 Correct 376 ms 8476 KB Correct
5 Correct 425 ms 8576 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 262 ms 8504 KB Correct
9 Correct 231 ms 8576 KB Correct
10 Correct 413 ms 8508 KB Correct
11 Incorrect 324 ms 6788 KB Incorrect string length
12 Halted 0 ms 0 KB -

Subtask #3
0.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 1 ms 348 KB Correct
4 Correct 0 ms 344 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 0 ms 348 KB Correct
7 Incorrect 0 ms 348 KB Incorrect string length
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 52 ms 2772 KB Correct
3 Correct 447 ms 8580 KB Correct
4 Incorrect 447 ms 8576 KB Incorrect string length
5 Halted 0 ms 0 KB -

Subtask #5
0.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 2140 KB Correct
6 Correct 6 ms 2128 KB Correct
7 Correct 1 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 1 ms 656 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 11 ms 2236 KB Correct
12 Correct 35 ms 1116 KB Correct
13 Correct 376 ms 8476 KB Correct
14 Correct 425 ms 8576 KB Correct
15 Correct 0 ms 348 KB Correct
16 Correct 0 ms 348 KB Correct
17 Correct 262 ms 8504 KB Correct
18 Correct 231 ms 8576 KB Correct
19 Correct 413 ms 8508 KB Correct
20 Incorrect 324 ms 6788 KB Incorrect string length
21 Halted 0 ms 0 KB -