oj.uz

Submission #1047552

# Submission time Handle Problem Language Result Execution time Memory
1047552 2024-08-07T14:01:10 Z Tsovak Sprinklers (CEOI24_sprinklers) C++17
9 / 100
 103 ms 7600 KB 
// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout << fixed << setprecision(x);
	return;
}

ll gcd0(ll a, ll b)
{
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

ll lcm0(ll a, ll b)
{
	return a / gcd0(a, b) * b;
}

bool is_prime(ll a)
{
	if (a == 1) return false;
	for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false;
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrtl(ld(a)));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrtl(ld(a)));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans *= a;
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}

ll factorial(int a)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans *= ll(i);
	return ans;
}

ll factorial_mod(int a, ll mod)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod;
	return ans;
}

// -------------------- Solution -------------------- //

const int N = 100005, M = 200005;
pr<int, int> a[N];
int b[M];
bool ans[N];
int n, m;

set<int> st;

int dp[N];
int from[N];

bool covers(int l, int r, int e) { return l <= b[e] && b[e] <= r; }

bool check(int h)
{
	int i, j;

	for (i = 0; i <= n; i++) dp[i] = from[i] = 0;

	dp[0] = 1;


	for (i = 0; i < n; i++) {
		dp[i + 1] = dp[i];

		if (covers(a[i + 1].ff - h, a[i + 1].ff, dp[i])) {
			j = ub(b + 1, b + m + 1, a[i + 1].ff) - b;

			if (dp[i + 1] < j) {
				dp[i + 1] = j;
				from[i + 1] = 1;
			}
		}

		if (covers(a[i + 1].ff, a[i + 1].ff + h, dp[i])) {
			j = ub(b + 1, b + m + 1, a[i + 1].ff + h) - b;

			if (dp[i + 1] < j) {
				dp[i + 1] = j;
				from[i + 1] = 2;
			}
		}


		if (i + 2 <= n && a[i + 2].ff - a[i].ff < h && covers(a[i + 2].ff - h, a[i + 1].ff + h, dp[i])) {
			j = ub(b + 1, b + m + 1, a[i + 1].ff + h) - b;

			if (dp[i + 2] < j) {
				dp[i + 2] = j;
				from[i + 2] = 3;
			}
		}
	}

	return dp[n] == m + 1;
}

void solve()
{
	int i, j;

	cin >> n >> m;

	for (i = 1; i <= n; i++) {
		cin >> a[i].ff;
		a[i].ss = i;
	}
	for (i = 1; i <= m; i++) {
		cin >> b[i];
		st.insert(b[i]);
	}

	sort(a + 1, a + n + 1);

	m = sz(st); i = 0;
	for (auto p : st) b[++i] = p;

	if (n == 1) {
		if (a[1].ff <= b[1]) cout << b[m] - a[1].ff << "\nR\n";
		else if (b[m] <= a[1].ff) cout << a[1].ff - b[1] << "\nL\n";
		else cout << "-1\n";

		return;
	}


	int l = 0, r = 1e9, mid;

	while (l < r) {
		mid = (l + r) / 2;

		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	check(l);

	i = n;
	while (i) {
		if (from[i] <= 1) i--;
		else if (from[i] == 2) {
			ans[i] = 1;
			i--;
		}
		else {
			ans[i - 1] = 1;
			i -= 2;
		}
	}


	cout << l << "\n";
	for (i = 1; i <= n; i++) cout << (ans[i] ? 'R' : 'L');
	cout << "\n";

	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:243:9: warning: unused variable 'j' [-Wunused-variable]
  243 |  int i, j;
      |         ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Correct
2 Correct 0 ms 2396 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Correct
2 Correct 14 ms 5468 KB Correct
3 Correct 1 ms 2392 KB Correct
4 Correct 19 ms 7096 KB Correct
5 Correct 19 ms 7180 KB Correct
6 Correct 0 ms 2392 KB Correct
7 Correct 0 ms 2396 KB Correct
8 Correct 3 ms 3420 KB Correct
9 Correct 0 ms 2396 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Correct
2 Correct 17 ms 5420 KB Correct
3 Correct 6 ms 2764 KB Correct
4 Correct 77 ms 7484 KB Correct
5 Correct 79 ms 7600 KB Correct
6 Correct 1 ms 2396 KB Correct
7 Correct 0 ms 2396 KB Correct
8 Correct 77 ms 4124 KB Correct
9 Correct 66 ms 4440 KB Correct
10 Correct 46 ms 6480 KB Correct
11 Correct 14 ms 2904 KB Correct
12 Correct 44 ms 6748 KB Correct
13 Correct 84 ms 5456 KB Correct
14 Correct 71 ms 6000 KB Correct
15 Correct 63 ms 5980 KB Correct
16 Correct 74 ms 4696 KB Correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Correct
2 Correct 0 ms 2396 KB Correct
3 Correct 1 ms 2396 KB Correct
4 Correct 0 ms 2396 KB Correct
5 Incorrect 0 ms 2396 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 0 ms 2648 KB Correct
2 Correct 34 ms 5464 KB Correct
3 Incorrect 103 ms 7256 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Correct
2 Correct 0 ms 2396 KB Correct
3 Correct 14 ms 5468 KB Correct
4 Correct 1 ms 2392 KB Correct
5 Correct 19 ms 7096 KB Correct
6 Correct 19 ms 7180 KB Correct
7 Correct 0 ms 2392 KB Correct
8 Correct 0 ms 2396 KB Correct
9 Correct 3 ms 3420 KB Correct
10 Correct 0 ms 2396 KB Correct
11 Correct 17 ms 5420 KB Correct
12 Correct 6 ms 2764 KB Correct
13 Correct 77 ms 7484 KB Correct
14 Correct 79 ms 7600 KB Correct
15 Correct 1 ms 2396 KB Correct
16 Correct 0 ms 2396 KB Correct
17 Correct 77 ms 4124 KB Correct
18 Correct 66 ms 4440 KB Correct
19 Correct 46 ms 6480 KB Correct
20 Correct 14 ms 2904 KB Correct
21 Correct 44 ms 6748 KB Correct
22 Correct 84 ms 5456 KB Correct
23 Correct 71 ms 6000 KB Correct
24 Correct 63 ms 5980 KB Correct
25 Correct 74 ms 4696 KB Correct
26 Correct 1 ms 2396 KB Correct
27 Correct 0 ms 2396 KB Correct
28 Incorrect 0 ms 2396 KB User solution is incorrect
29 Halted 0 ms 0 KB -